I recently released my first android app. However, there have been only three downloads. How did you get the first couple users of your app? Did you buy ads to promote? Or were those just random users who found your app in the store?<p>(FYI: https://play.google.com/store/apps/details?id=com.johannes_mittendorfer.abfahrt)
Use your social network, write down a press release about your app and send it to blogs interested in the subject. Don't send a bulk message! Be creative and personal for each blog you contact.<p>That's my 2cent about this, it worked for a little experiment I made some times ago<p>Best of luck!