You can do it with a smart contract. Place the user's funds in a smart contract that takes
- A lambda returning a list of operations
- A counter
- A signature by a given key of the above
(technically you don't really want to explicitly pass the counter, you can just assume the one in your storage is the one that was signed)
- Checks the signature
- Checks and updates the counter
- Executes the lambda and return the operations
This would be very similar to the manager.tz contract except that instead of having the access controlled by checking SENDER, you control the access with a signature and a counter.
Now, have the user produce the lambda and the signature, and any third party can pay a fee to inject this payload into the contract and trigger transactions.
A more direct way to do that would be to allow manager operations, which already represent bundles of operations, to involve multiple accounts and multiple signatures so that the fee can be paid by another party. This would be a small, but useful protocol upgrade.