Discovering a block is basically done by solving a problem that is hard to solve, but easy to check (think a really hard sudoku). There are still a myriad of problems that fit this description but that are not used in cryptocurrency hashing.
So here's the thought. Why not use the proof-of-work calculations to solve a problem in machine learning? Many problems in machine learning are hard to solve but easy to check. One such problem is training a machine, e.g. a big neural network. Discovering a block would be mean producing a set of weights that allow the network to validate a test data set correctly. (I'm leaving out many practical details here, such as how to treat hashes.)
Another approach may be to treat the entire network of crypto miners as the machine itself, and use it e.g. to detect interesting instances, such as in SETI, though that example may be too esoteric.
[Update 2014/07/29: I'll be pasting some remarks here that have appeared on other social networks in an effort to centralize ideas.]
Specific properties of the computations in typical proof-of-work:
- Solution is hard to obtain but easy to verify;
- Input data for the computation depends on the block / transaction data;
- A small change in the input data triggers a big change in the solution.
"Block-finding is like winning the lottery and mining throughput is proportional to the number of tickets bought."
So how about formulating a problem that rewards intelligence instead of computational power, possibly maintaining some of the properties listed above?