1) Replace the pointless hashing with some actually useful calculation or form of work. Trouble is, I'm not sure what kind of asymmetrically difficult function could be used instead of hashing that would have some value for society.
2) Replace the hashing with some kind of genetic algorithm or other AI solution search. So instead of trying to find the proper hash, you're trying to find the proper algorithm to some currently-posed problem. Miners who find the current-best solution can then be rewarded with some form of bitcoin, which can be traded among themselves as currency, or used to decide what the next problem the network searches for a solution to will be. I figure this would make the entire blockchain into a giant sort of AI/brain, with the problems it tackles being more or less democratically chosen by whoever wants to spend the most of their bitcoin for it. The spent bitcoin then goes to the people who find the best solutions, in addition to whatever small amount of new bitcoin is mined. And replace "bitcoin" with whatever the new name would be, of course.
May be possible, maybe not. There's basically no chance I'll be able to implement some version of either any time soon, so feel free to run with it if anyone thinks they can.