It's actually a soft fork to change the consensus method believe it or not, even changing to a new proof of work scheme is completely backwards compatible. It's not a good idea and it's sort of ridiculous, but it is technically doable. If you felt inclined, we could change the transaction format, switch the scripting language to x86 assembly, issue new currencies- all in a soft fork.