This is a tough one, and I think it's possible to find a solution to it, but it will depend on what your application is and the tradeoffs you're willing to accept.
Using Bitcoin, you could fund an account for your users, but it is far from ideal. I have done this before, I do not know of a service that offers it, and I don't recommend it. Pretty much you need to anticipate a user's usage and fund accounts before they take actions... If you don't pre-fund accounts they need to wait for transactions to confirm, because if they don't wait for the funding to confirm, then the funding transaction may be malleated and their signed transaction relying on it is invalidated. I guess this isn't the worst thing, but it makes for a very strange user experience where the user has to wait X block confirmations to sign off and actually initiate thier action.
You can ease this a bit by pre-funding an account, but you run into the problem of predicting usage, and if you over-fund your user you are effectively burning coins(in the worst case where they leave your app and never use it). One way to avoid burning is to give the user a 1-of-2 multisig account, where your user has a key, and you have a key to recover funds they don't spend in the future(maybe not acceptable in your use case for you to have a key to the user's account). If you under-fund, your user cannot take actions until you further fund them. On top of all that, pre-funding is messy because you don't know what transaction fees will be in the future.
In the future:
Some of the above problems are eased by the malleability fix of SegWit, assuming it gets activated. I think Covenants may also be worth looking into, but it is probably even further down the road.
What would really solve your problem is the planned account abstraction for Ethereum's Serenity(see "Abstraction and Accounts" section, or this EIP). Essentially the ability for zero fee transactions is introduced, where instead of the user initially paying the fee, the contract the transaction is sent to can pay the fee. This would then just require you to write and fund a contract that funds any transaction sent through it for transferring your tokens.
It is still early days for this stuff. I'm curious to see answers from other people/on other blockchains, but I imagine what you describe will continue to be a problem for 3rd party apps built on blockchains.