Wait, no Heroku? It should definitely be listed in the Price-Scalable Hosting section. Like AppEngine it's also free starting out, and super easy to scale. Plus it's all rails, so you don't even have to learn any App Engine API.
2 x processes + 20GB database = $51/mth
Most people won't require every addon, and there's a free or cheap option in every case. Yes, you can spend "hundreds of dollars a month" but not easily
It jumps to more than $200 if you want just one more Thin process or a background worker, etc.
I'm not saying that there's anything wrong with Heroku's pricing, but I wouldn't considering it a "cheap or free web-based tool".