1. Покупаю немного мотивированного трафика, чтобы, во-первых, появились какие-то установки и гугл увидел, что пользователям интересно, а во-вторых, чтобы появились отзывы — без отзывов будет сложнее делать рекламу.
2. Размещаю на бесплатных ресурсах, на 4PDA например.
3. Покупаю «нормальную» рекламу. Тут вариантов масса — фейсбук, директ, myTarget, AdMob и т.д. Честно говоря, все не очень в плане «юзерфрендли» (поддержка никакая у всех, объявления могут не пропустить просто так и ничего не докажешь и т.д.). Конкретный канал порекомендовать сложно, т.к. они разные для разных приложений.
Важно ко второму шагу стабилизировать приложение, чтобы реальные юзеры не сталкивались с крашами на каждом шаге.
Бесплатно же вряд ли получится, только если случайно завирусится, но такое — один случай на миллион.