"Double spend = same input, different outputs."
You would still need to reconsider the changed tx fee. That would require you to change the amount of the "change" adress, and/or add new inputs and/or outputs to the transaction (if the too-low-fee transaction also included inputs with too low value to be able to increase the fee) so the new fee add up correctly in equation.
Its hard to check in a safe way. I think a tx expiration feature would be better then.
We could allow the amount of only one output to change. The only thing they can do with that is change the fee, they can't take any money back.
I prefer a cleaner way to increase the fee that doesn't require messy double spending and can be done by either side: The recipient can spend the low fee txn with a larger fee so miners have to include both transactions to get the larger fee. The payer can also do that by spending the change.
Unfortunately, Theymos is right, tx expiration is not possible.
I think the proposal have a flaw, consider next scenario.
1. Transaction 1 is broadcasted
2. Merchant accepts Transaction 1 with 0-confirmations and release the purchase
3. Transaction 2, which is double spend of Transaction 1, is broadcasted
4. Miner gets all the coins from Transaction 1
5. Merchant eats the loss.
The customer doesn't get anything back by doing that. There's no incentive.
If you believe as some do that miners can be bribed with fees, then that's already possible. The customer could double spend it all to fee.
The double-spend-becomes-fee model is strictly superior to the fee bribe model. Under fee bribe, part of the payment can be taken back by increasing the fee.
Under this new model, any attempt to steal a payment back becomes proof the miner can use to take the whole amount. Under both models, they can give the entire amount to fee, but under this model, that's the only thing the double spender can do. He can't benefit from double spending.
