I don't know how often ER_LOCK_DEADLOCK will occur on a Drupal website - but we should be able to handle it.
ER_LOCK_DEADLOCK is mysql-specific. I don't know if other engines have something similar. We should have an exception that is thrown in this circumstance, regardless of which engine type is being used.
It might make sense for each transaction to be wholly contained in its own function. As the function's local variables will be reset each time it is called, it will be easier to write transaction functions that do exactly the same thing during reattempts.
We could then have a function called execute_transaction() that would repeatedly reattempt the transaction function if it fails due to ER_LOCK_DEADLOCK.