4) Lazy marketing: Hm. What steps would you take to promote an iPhone (or Android) app, assuming it's a well-made app that doesn't fall into the categories 1) to 3)?
Here's some starters. Note that none of these cost anything really, unless you outsource any part of this:
0) One little way I've seen some devs do it, and this isn't really true of everyone, is they have a developer blog or diary with little snippets of code or screenshots or balsamiq mockups or character sketches for games, to build hype. I see streetwear clothing brands do this all the time, and it captures the energy of the product before you even see the finished product.
1) Get active on boards and social groups that have alot of members that would take their interests to their phone. If you're an automobile mile-per-gallon (MPG) calculating app, frequent some hypermiling or green-car (or even general automotive) blogs and forums, get active, and then tell the site admin that you've got an app for that and that you'll promise them a promo code if they can review it. Be prepared for all kinds of tricks back from them (especially if the site is popular). If you want to make a deal (payola review, promotion, etc.), go ahead and make it. You don't generally have to do much with the smaller niche sites, though. A promo code will probably do it. You can also PM one of the board moderators or senior members if they want to take a look at the app as well. Could be worth it.
2) This doesn't really work with games (though it could, I guess), but if it's not a game app, SEO your product website, per instructions on patio11's blog: http://www.kalzumeus.com/2010/07/17/seo-for-software-compani...
3) When it comes out, Facebook wall, tweet, prweb announce, etc the launch. The usual stuff that $19.99 "e-marketing" ebooks tell you to do but you should know from reading HN every day anyway :) That stuff's easy.
Generally the strategy is send out promo codes to blogs which can provide an uptick for a few days.
Besides that you should probably try and introduce social features to the app such as facebook/twitter.
Another option is the rising number of pay per install services. My own startup adsreloaded.com (/end shameless plug) is involved in this area, as well as other companies such as apperang, or Flurry's appCircle.