For instance, you could keep track of the configuration history - when adding a shard, you create a new version. And when trying to fetch, you could try the latest version of your configuration (which says, for example, that it's on server 3) and if not found you could try the previous version (which says that it's on server 1). You can also add the possibility of removing a shard, however this requires that for every write you'll have to do a secondary write to another server, for redundancy.
In the background you could have a healer that whenever a new version gets pushed, it would go through all entries and move them accordingly. And at the end it would declare such a version to be "healed".
However, what I described above works in case you want to introduce a new server in production immediately. Like say, in the case of something like Twitter, you want to write to the new shard right away and the most important messages are the most recent ones. But you may also want to create a configuration such that a new server isn't hit by the front-end until the healing script hasn't finished migrating.
The thing is, a layer like this gets to be very optimized for your needs and there's no one size fits all.
The big limitation is that your DB structure has to be hierarchical. I think a lower-level solution at the WAL level would be better.
You can look at PL/Proxy that makes some things related to partitioning across multiple machines easier.