App stores will never remove the need for other advertising. Why not send review copies to the major Android, tech, and gaming websites, and see if they put something up? Why not put something up on AdMob? Why not do giveaways of the game? Why not put it on a competing app store? There are many legitimate answers to these, but relying on the Google Gods to sell your product for you is just silly. (Whether Google's cut is then justified is a different matter entirely.)