You are forgetting some really simple cases like:

1) My friend has one

2) I saw one at a party or work function

3) I was at the store a while back, browsing around (of my own volition), and learned about them

I could go on, but you get the idea. There are very many ways to learn about new things other than overt advertising. If we are being lenient, it's actually not too different from asking "how does culture spread and evolve?" Humans have been doing this stuff for thousands of years.

To address the second half of your post, I do agree 100% that it's impossible and unreasonable to draw a really hard line against all advertising. But I think we can certainly do way, way better than we do now.