The problem with the solutions you suggested is that there is no easy automatic trustless mechanism for demonstrating proof-of-work. Edit: Of course, if you don't mind some centralization/trust, then your suggestions could theoretically work.
One altcoin called primecoin has a proof-of-work algorithm which finds long runs of prime numbers, which is supposedly useful for some purposes.
The most common alternative to proof-of-work mining is called proof-of-stake, which is used in a few altcoins (most notably Peercoin). It still doesn't provide anything useful, but at least it provides a mechanism for securing the blockchain without wasting a bunch of energy. You can read about it here:
https://en.bitcoin.it/wiki/Proof_of_Stake