This wouldn't work, because a miner can easily pay himself any amount of bitcoins that he has saved up in fees, and include this transaction in his own block (not broadcasting it). Thus he can basically create these "deposits" for free, and sell them for a profit.
That's the thing: whatever you try as a counter-measure, you always come back to money: in the above scenario, money would replace "deposits" because "deposits" would just be sold on the open market for money. Proof-of-work becomes money: if something important requires proof-of-work, you can be sure that a web app would surface that performs proof-of-work in exchange for money.
It always comes back to money, because whatever restriction you put on something, whether it be "pay fee to Bitcoin miners", "Solve proof-of-work puzzle", or something else entirely, these things will always end up being sold for money in an efficient market, because of the increased efficiency of division of labor: why should I use my inefficient smartphone to calculate proof-of-work, when I can pay a service with custom ASICs to do the job for me at a fraction of the cost?
As far as I can see, the only alternative that can work besides money is something that cannot be sold for money. And I can't come up with anything that fits this requirement.