Why isn't a dependent transaction which pays a fee all that is needed? This requires no dropping of existing transactions.

1. A+B -> C + D
2. D+E -> F + (G - Fee)

In this case the Fee pays for both transaction 1 and transaction 2.
The only problem seems to be if you make a transaction with zero change and then want to add an additional fee. But that is up to the choice of the sender anyway.