Now a way around the centralized nature is if you can create a molecular hashing algorithm where the hash of a string is some random protein. Then the first one to fold it wins the block. Benefits to this is you are doing 'useful' work but the downside is no one probably cares about folding that random protein.
Although you do have foldingcoin and curecoin the folding@home project does predate bitcoin by about a decade. These coins have set themselves up as a reward system for a project hat was going on for years before.
As for changing the way BTC works, I am with @mynonce here, this would be an altcoin.
I have been seeing more and more people talking about changing the way BTC is mined, and at this point I am beginning to put them in the file of 'people who want the magical internet money for free, because I want it'
Mining will be at a cost and not a small one at that.
-Dave