The only way I could think of adding PoX into Bitcoin without a hardfork is to keep PoW as it is and add PoX as an extra constraint which is stored in the coinbase scriptsig perhaps. If the majority of clients are new then the blockchain will be validated according to these new rules but the small proportion of older clients will still validate PoW as usual. However, if the difficulty decreases due to the extra constraints then there's the potential for an attack on old clients by ignoring the new constraint and just mining PoW.
That said, I don't think that is an elegant way to do it. Have there been other suggestions?
Here's a simple way you can make it into a soft-fork change: compress HEIGHT, GREATERTHAN and VERIFY into a single opcode that doesn't have to modify the stack. Then you can re-purpose one of the NOP opcodes.
Proof-of-burn as usually described doesn't change bitcoin's validation rules, at all. I'm mostly aware of its usage in higher level protocols such as identity protocols which simply reference the burnt coins and maybe some data attached to them in the OP_RETURN output.
Proof-of-stake as
originally described didn't require any protocol changes either. It is simply a mechanism for counting votes for or against a proposition (such as checkpointing a block) by weighting those votes according to the coins the pubkey signing the vote is protecting. This is a higher level protocol which can affect the client / wallet operation, but not the actual validation rules so no fork is required.
If you integrate proof-of-x in with mining, then yes hard forks are required. But why do that? It ends up weakening security instead of strengthening it.