As Slava mentioned, you can use Compose.io. It requires using an SSH tunnel, though, which is a little tricky in Heroku. Here's a tunnel script I made to simplify this:

https://github.com/fanout/leaderboard/blob/master/tunnel.py

In particular, it reads the entire SSH private key as an environment variable, so you don't need to commit the key to the git repository.

You can spin up RethinkDB today with https://www.compose.io/ (it's surprisingly easy, and their support is awesome). It should be pretty easy to get a RethinkDB Heroku plugin based on Compose. If the community doesn't get around it, we can probably do it internally pretty easily.