Digital signatures are a simple example (e.g. opensig.net): The user buys tokens in order to write the hash of a file to the blockchain.  In this case it is the blockchain itself that provides the service and the miners receive the rewards.

There are many decentralised applications too.  You're right though, if the developers of these apps are trying to make a profit then they could charge something on top of the transaction fee or sell tokens to the user at a premium.  I'll think about this more.