These are the kind of issues that I hate dealing with and would make me consider hosting on a platform as a service like Heroku. Does Heroku have auto sharding IDs built in?
If you're using statement-based replication on Heroku, it still won't save you. I have no idea if you can or can't do so. Statement-based replication seems to be one of those things where you can shoot yourself in the foot if you don't design with it in mind.
While there are (or at least were) some third-party MySQL add-ons on Heroku, in general Heroku uses postgres instead. I have no idea how/if these issues apply to postgres.
Heroku offers one database management system right now: Postgres, and its principal replication technology is not based on statement-based replication, and largely for this reason. Using something like PGPool can make the problem come right back again.
So, I will say that the only credit Heroku's staff (which I am a member of, perhaps pertinent to this opinion) gets is for reviewing the technology in play and deciding something like "supporting statement-based replication is basically going to lure a lot of people into a place they don't want to be," and then ignoring statement-based replication entirely. The same general opinion can be said to have been held by PostgreSQL.org, I think. I also want to stress the fact that statement based replication is only but one form of "logical" replication (as opposed to "physical", like the crash recovery logs), and there has been no shortage of interest in the logical replication feature in-the-works (but won't be seen until 9.4 at the earliest) based on crash-recovery log decoding. The design of that should allow exactness to be in principle possible modulo bugs.
The decision to ignore statement based replication has not been without cost: many simple workloads can work with statement based replication, and it would enable support for (with those simple workloads) on-line upgrades to new database versions sooner, but the bizarre (and silent) ways in which statement based replication can break and the seeming impossibility of making statement based replication predictable and exact stayed our hand. Many people fail to read fine print or, sometimes, even big blinking warnings, so inevitably there would be a lot of aggravation for those affected and the staff, who will have to tow a fine line between "told you not to do that..." and digging into a problem that was caused by unsupported use of a feature to assist in fixing it (on a case by case basis, for something like this probably) so everyone can be somewhat more happy. This is no fun for all involved, and when I can see it coming, I try to avoid that position. That said, not everything will be foreseen...but such is software.
