I think you will always need internet advertising for your app or nobody will know about it.
I have not published any apps yet but here are the steps I think I will take:
1. Upload Beta to market
2. Promote Beta on forums (like b4a,xda) to get some feedback on the app so you may change it if users feel so.
3. Wait a while so all problems are ironed out and you find out what devices are not supported etc and then update the app to final.
4. Have a website/blog where you promote it. Get backlinks with other developers. (Maybe we should have a section for that in the forums).
5. Start promoting your app on various internet blogs. For e.g. start with Android sites like androidcentral, androidpolice etc etc, there are a lot.
6. Wait a while to get feedback. Then promote it on more bigger blogs like lifehacker, addictivetips, techcrunch. Okay, maybe going tooo far but well, you have to try. Also if your app is related to something (for e.g. medical) so try promiting on those websites.
7. When you are finally out there, you can also try getting on the featured list. Im not sure how though.
8. I have also noticed, the more you update your app, the more downloads it drivers.
Not sure what else you can do...(maybe use social media:FB,Twitter)