Instead of mining, those who want in put down a stake of ether that they can mine it and get a better chance of winning based on the size of the stake. If they get caught cheating, they lose their stake. There probably going to be some fun when the first serious exploits happen (oh shoot, what happens if someone does [whatever]?) but I think the premise is solid enough that it's worth trying.
I do still have serious concerns over things like the DAO hard fork and the expectation that non-expert developers can or should be writing smart contracts, etc. Ethereum isn't perfect. But if they can provide the same service without the need for mining, all the power to them.