Multiple proof-of-work algorithms.
SHA-256, mergeable with Bitcoin.
Scrypt, mergeable with Litecoin.
And N additional algorithms at your option.
Give each a separate difficulty, adjusted to make it constitute 1/(N+2) of the blocks mined.
That way, if one of the PoW algorithms gets broken by an attacker, it's not enough, in and of itself, for them to successfully double-spend.
Are you saying that the proof-of-work changes every block. So it starts with SHA-256, then scrypt, then something else?
How does that make it more difficult to double-spend?
I can see by adding a CPU only proof of work, it gives miners incentive to use the excess capacity of their rigs to mine the coin.