2) Create Twitter searches to find people with the problem your product solves, and tweet them your solution.
3) Establish yourself as an expert in relevant forums and leave a link in your forum signature. Connect with other forum members.
4) Do giveaways in relevant blogs. Tie the giveaway to your web app in a creative way. You don't necessarily have to giveaway a premium plan of your product - it could be another product, or an Amazon gift card.
Protip: I know from experience that doing a giveaway > $100 and posting in in online-sweepstakes.com will yield over 100 0 visitors in a day.
Give more entries for retweets, facebook likes, etc.
5) Guest blog posting is easy low hanging fruit.
6) Do cross partnerships with another startup.
7) Find a similar new product in your space. Search Google news for stories on that product. Pitch your product to those same writers. Make sure you develop a relationship before that pitch.
8) Encourage existing users to share it through email. Give them call to actions.
The people who care about what you've built and are going to evangelize it for you aren't your friends and family or the people who see you on an ad platform, it's the people who's problem you're solving. If you already know who they are, and if they think you're as valuable as you think you are, then add incentives to their sharing with their friends. that's why gamification is the new big thing these days...
if you haven't found your customers, and i mean real people with names, not just the demographic or psychographic that is in your business plan. If you've found 2-3 people, then get them to use your product. then get feedback so you can make their lives even easier. as part of that feedback, give them the option of inviting others into the circle.
you can also go the easy route and get in touch with a mashable or TC writer. Even a small blurb will get you a bunch of random signups, 80% of whom will unsubscribe from your list and forget about you 5 minutes after they sign up.
How is this so? Care to elaborate upon this a bit?
You should start marketing the product as soon as you start writing code. Start collecting email addresses, writing blog posts, talking to people, etc etc.
When you launch you should ideally have an email list which are already interested in your product. These people are your lifeblood. They will tell you what sucks about your product and what to change. They will tell you that your product isn't what they need...but they will provide critical information about what they really need.
Code is only 20% of the battle. Marketing is the other 80%.
I'd say the difference between "lost" and "seriously far behind" is comparable to a "broken heart" and a "not-so-broken heart".
Spend some time talking to your target market. Based on that audience, you may be able to come up with a more creative (and less expensive) way to get users in the door. It's a slow, steady trudge until you get traction.