Couldn't this be implemented as a UASF instead? The SHA256 side can be rendered insignificant from the get-go and blocks would still be backwards compatible.
That would be pretty risky on a flag day without knowing which side every service and exchange would take. The argument for a HF is politically harder. This is silly, but it's the current status of the Bitcoin culture.
Maybe as a progressive but relatively quick PoW switch as a SF, it could be done. As Maxwell describes here:
https://www.reddit.com/r/Bitcoin/comments/60j1zi/bram_cohen_bittorrents_creator_a_soft_fork_change/df6snyy/This may be the best way to get a POW change started as it gets everyone used to the idea. If things go south quickly, I'm sure the transition could be accelerated through another SF (more palatable at that point) or even an emergency HF.
Actually I had not thought of going about it in this order and it makes an awful lot of sense.
I was thinking in having the contingency ready for the sudden one and the longer term progressive one to be applied in a more "relaxed" period. But actually the "I'm altering the deal, pray I don't alter it any further" approach makes even more sense from the incentives point of view.
-----
As for intricate, not proven combinations of multiple algorithms: I'd stay away. More risk that some attack vector is discovered in the future.