It sure isn't easy!
First get as many friends to download, G+, and rate the game as is possible. This tends to take a bit of time because... people are busy with their own lives! There are some Facebook groups and Google+ groups where you can exchange reviews with each other and promote your apps. These are pretty good but take time and you have to be cautious and ask for honest reviews, don't ask for 5 star reviews as that might be seen as manipulating the system.
G+'ing is VERY important as it really helps your ranking and when doing a regular Google search your app will come up more.
Next up is link building... this is even tougher! You need to get people to write reviews about your game and blog about it with links to the play store. All I can say about this is that you need a really good app that is newsworthy. If not you'll be begging a lot for very few reviews. Try aiming at the lesser known blogs and review sites. They won't get you very far, but it gives you more credibility and helps when you're asking others for blog reviews.
Search Google for "Gamasutra article on Google Doc for Indie Developer Help List"
I can't post a link yet...
That list is AWESOME!
Next up is to try some alternative markets. SlideMe, GetJar, Opera, and Android Pit have their own app markets. Even if you just get as many downloads from them as you do Google Play then you're getting somewhere.
Finally make sure that you have a press page all set up so that when people do want to review your game that the relevant info is right at their finger tips! check out dopresskit by Rami from Vlambeer.
That's about all I've got. None of it is easy. But keep at it. Work at getting FB and Twitter followers. Try to have fun with it!
Thanks for the Gaasutra list, found it and it really helped me out