It's been a while since I've tried to market a new app.  With the introduction of CrazyCat on the Android Market, I've started paying attention again, and things have changed significantly.  While the new Android market looks really slick, I must say that Google has really kicked the small developer in the teeth with the format of the new market.  

Most notably, there is absolutely no way for devs to get a paid app in front of customers using only the market.  In the past, Google prominently promoted a "Just In" category on the market.  If you released or updated an app, it would show up (with certain caveats) in this highly-visible place on the Market.  If your app was good, lots of people would download it, it would start trending up in the market, and money would start showing up in your Google Checkout account.  It's only been a couple of short years since the Android Market started allowing the sale of apps, but already those are the good old days...

 Well, "Just In" is gone.  It's been replaced with an "advertise this app" link in the developer console of the Android Market.  My assumption was immediately that Google has given up on the idea of making money off of app sales, and decided instead to start squeezing devs for some advertising revenue.  Consequently, they removed the market promotion mechanismsthat pretty much everyone had learned to game.  It's very curious, however, that Google only allows integrated advertising of FREE apps.  You can't advertise paid apps using AdMob, at least not in any kind of direct and automated way.  That leaves devs with no choice but to look outside of Google for mechanisms to promote their apps.  Here are some ideas that I've found productive in the past, and am using again for CC.

1. Use Flurry AppCircle.  The Flurry model is a million times better than AdMob for paid apps.  You bid to have your app advertised at a fixed price, but are only charged per install.  That allows you to build the cost of your promotion into your app price.  A large number of installs generated from this type of service can get you on one of the Market's user-visible categories such as "trending".  

2. Get Reviewed.  This isn't as easy as it used to be.  It seems like the Android review sites have gotten very busy lately, and it's difficult to get their attention unless you want to pay for advertising.  A review or two can give your app a baseline income for years to come, so keep at this one.

3.  Go Social.  Creative use of Twitter, Facebook, and to a much lesser extent for now, Google+, is still a very powerful tool for app promotion.  Build yourself a following on social platforms, and then judiciously promote your app using engaging content such as videos.

4. Establish a Web Presence. This is really important for the long-term health of your app.  Given that Google gives you no way to get your app in front of users using the market once you fall out of the top 100 (or whatever the number is), you need to have well-placed content in the form of blogs, forum entries, and YouTube videos that will match keyword searches and direct users to your app.  One trick I use is creating a Google news alert matching my app's keywords.  As soon as I see new articles that are topically related to my app, I make comments on those articles to direct users to my app.  Authors generally don't mind this as long as the comment is relevant to the article.

So what do other devs do?  I'm curious to hear other marketing tricks in this brave new world where Google has eliminated the Android Market as a way to get apps in front of users.