There's primecoin, which uses a proof of work based on finding a special kind of prime number, which (they claim) has use in the outside world, at least the academic one.

https://en.wikipedia.org/wiki/Primecoin

Generally, to have a useful PoW, it needs to meet some criteria:

1) Easily verifiable

2) Necessary work on the problem is easily quantifiable and estimable

3) Problem can be programmatically generated from random data.

One model might be NP-complete problems. Users feed in problem instances they want solved, with a bounty. You find out how many guesses it should take. A valid proof of work then requires solving enough such problems, combined, to exceed the difficulty threshold. (You'd also need to solve one based on the current known transaction history.)

The problem there is that it's hard to know if a given NP complete problem instance is "one of the hard ones" and to find such instances.