I think a lot of non-technical business people and journos didn't fully understand that the Bitcoin blockchain is more than just a Merkel tree, and so have started using "blockchain" to mean a bare MT, despite the fact that the blockchain in Bitcoin is only meaningful because of how it's computed.
So maybe proof of work can be replaced, but without some consensus protocol it's not a blockchain in any meaningful sense.
"Merkle graph" may be a better term, since both Git and Bitcoin may have multiple hash references to the same node [in some sense].
I pretty much agree that "some consensus protocol" is probably the right place to draw the line. I'd add "decentralized", in the sense that no single entity can control the "consensus", which I think may be what you mean: "some decentralized consensus protocol".
So maybe proof of work can be replaced, but without some consensus protocol it's not a blockchain in any meaningful sense.