What I would really love to see in a solution like this is the ability to automatically rebalance shards (like moving data between shards when adding new instances).

Sharding can be achieved quite easily on the application level, or by using one of the few available proxies. On the other hand, re-balancing is not easily done yet.