Very interesting thread, I think every starting developer have these problems.
As my first time doing this, all I have is what I read from forums, so I can't be sure of what works and what doesn't, but it makes some sense and it's worth a try.
- As some people said, social network, post updates and interact with your customers.
- Contact reviews sites and ask for a review. Although most of the time you won't get an anwser if you ask for a free review.
- Frequent updates
And I read about a crazy idea from a guy who just made a bunch of cards of his app and started distributing it all over the city, leave on restaurant's tables, giving to waitress when he paid the bill, leave a stack on coffee shop's counter and bus stops.