Out of interest, can pools take requests and manually include TXs, as you describe?
If so, maybe an automatic service could be set up whereby we can add TX fees at a later time, by getting all the major pools to subscribe to a list of fee free Txs that have had a bounty paid by the user to get included in the blockchain. Which ever pool does first, gets the bounty.
That's an excellent idea.
The person providing the bounty might not necessarily be the person who sent the transaction. It might be the recipient, or even a third party who has agreed to do so just to help someone out. A system like "send your BTC amount to to add a bounty to this transaction" might be the cleanest solution... though of course that particular transaction would need to pay a fee...