First of all, I want to say that I have no experience in promoting Android apps. But I did some work in promoting websites for businesses, and I can suggest some things.
Key is a having a functional app. If users download an app which is half done and has disabled functions because they aren't done yet, they are going to uninstall it. Second suggestion, a great design is makes a difference for a lot of people whether they're going to install it or not.
When you have both those things, you can get on with actually promoting the app. I would search for an SEO copywriter to get the description for your app. SEO copywriters are specialized in optimizing texts for Google. And I would look into advertising on Facebook. I think you can actually promote your apps, and advertise only on phones. This way your advertisement will only be showed to people who are using Facebook on their phone. User will probably more tempted to install the app.