having proof of work or not is orthogonal to whether it's a blockchain or not. see: blockchains for proof of stake cryptocurrencies.
So maybe proof of work can be replaced, but without some consensus protocol it's not a blockchain in any meaningful 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".