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.
The more I think about it the more I believe a SF PoW change is the best option -- even in an emergency. It's the least disruptive to users and businesses with alternate clients. Exchanges, wallet providers, etc should only need to set up a border node and they'll have all the time they need to upgrade their legacy systems. AFAIK, this can't be done with a HF and would cause a lot more economic disruption.