AFAIK there's nothing stopping you from using Amazon's SimpleDB, especially since Heroku is already running on EC2.

Also, given the "SQL Databases Don't Scale" by Adam I would be very surprised if they don't roll out a more "scalable" alternative to Postgres in the near future.

I don't think it has yet.

It's really easy to connect to hosted NOSQL environments though, if that's your cup of tea. AFAIK there are some solutions for most of them: MongoHQ, Couch.io and another one for Redis I can't recall.

You could also do it yourself. Basically anything that is also on EC2 shouldn't affect performance too bad.

It hasn't changed (yet?), but you can always put your NoSQL datastore on your own EC2 instances. Or you could use it with something like MongoHQ (http://mongohq.com).