How do we explain to Bob that he doesn't get his donut without resulting in a fist fight, a discrimination lawsuit, an all day seminar on the technical workings of the blockchain, giving away a free donut, and/or potentially losing Bob as a regular customer?
You probably won't be able to so the only solution is to prevent it from happening to begin with.
So basically stop accepting 0-conf transactions for all purposes, even from trusted customers, until all wallet software has been updated to not spend unconfirmed change? This seems like an extremely severe setback for bitcoin adoption and its utility in general.
The issue isn't 0-conf transactions. It is 0-confirm tx which use as their inputs the unconfirmed outputs of another transaction.
All Bitcoin clients ALREADY prevent the client from spending unconfirmed outputs for lots of very good reasons. However since the wallet can "trusts itself" they wallet makes an exception for unconfirmed CHANGE. Obviously no user is going to double spend themselves. So the prior tx will eventually confirm and that means the change will eventually confirm as well.
Except if an attack mutates the original tx, then the original will never confirm, the duplicate will. That means the change output is now invalid and the subsequent tx will never confirm.
Simple version:
This isn't about 0-conf tx. This is about transactions using the as their input 0-conf outputs.