You could certainly use advertising to collect email addresses, and then call those people to figure out what they want. The reason I don't like that as much is it puts another layer of specialized skill between you and your prospects. You have to dump a bunch of money and time in to learning how to write correctly targeted ads that convert before you even know who you're trying to convert, or what they care about. That's a tough problem to get around for most people.
If you're going B2C or B2SmallerWebsites then you're aiming for much less per sale, and therefore to get legs you'll need to be able to sell to a lot of them. So potential sales targets are all around. You won't be able to find them in sufficient volume to make a difference until after you have advertising turned on. But you still need to figure out your business. And talking to people in person is a great way to do that.
Also you should read http://www.paulgraham.com/startupideas.html. Pay close attention to the section labeled "Well". Odds are that, no matter how much you like your idea, you've chosen a poor idea to make a startup out of. Try to find a more focused variant to start with.
I spent a year work on a product based on some informal surveys and a lot of assumption. Luckily it doesn't cost me a lot to run it, so I can keep it going and continue plucking away, but while it was a good learning tool, I also learned that trying to find a niche would be much nicer to start with.
Thanks for the link.
If you're selling a horizontal product targeting customers where their existing technology they use could tip you off (e.g. companies that use Marketo and Mailchimp), LeadLander and BuiltWith are useful.
Once you get a list of target companies, the next trick is finding the right person to sell into. If you know their title, search Google like this:
site:linkedin.com "Company Name" "Title"
That works well since it lets you plow past Linkedin's limitations on searches outside your personal network.
Once you figure out your customer's company, name, and title, head over to email-format.com or data.com to look up the email format for the Company. With Rapportive for Gmail, you can take a few guesses and usually find the right person. Or read this post: http://www.distilled.net/blog/miscellaneous/find-almost-anyb...