Facebook, Google and Twitter offer app install ads and this whole area seems to be in a very dynamic time currently. Because the app stores are somehow still "Yahoo 1998" - they feature top lists and apps in categories. There may be wonderful apps hidden somewhere that are simply not discovered by anyone. How bad it is can be seen here:
If Apple or Google feature you in their stores - it is basically the your only chance to be successful without investing trillions in advertising.