Can you just store the shard id for each user in a database? Each server could check if it is authorative for each incoming connection, and redirect if not.

That way, you can migrate users one by one (sending a 'redirectUserConnections(userId)' to the original server, and even pick a shard that is geographically close to the user. (If you care about race conditions during migrations, you need to be really careful though.)