Having just seen this it at work for a startup we helped launch, I strongly recommend (without giving too much away):
5) Makes sense for other companies to promote to their customers. Ideally ones with lots of customers.
Bonus points: your product fits in to their customer acquisition process (i.e. helps generate more revenue for them).
Triple bonus points: you have access to a large number of these companies through a small number of entry points. For instance a trade association or a friend that will introduce you.
You wouldn't believe how easy it is to get your product out there in the above situation. PR is the last thing you worry about.