There are a number of other systems that allow this same approach of consistency and high availability. For example, Cassandra, which is freely available (as required by the poster), appears to be able to give you this behavior if you set ConsistencyLevel to QUORUM.

Clustrix, the company I work for, offers a full SQL data store with similar quorum semantics. However, it's not free.

Google Megastore allows similar consistency semantics (with its own data model) in a cross data center "cloud" fashion. It's also not free, but it would probably be suitable for some set of Heroku customers, particularly if they're already using Google App Engine.