If the mining reward was suddenly changed to 0, and there were no mining fees anymore, what would happen with the Bitcoin network? Assume there is another anti-spam measure in practice (ex: a tx would need the last block hash + some small PoW on top of it). Would Bitcoin suddenly collapse and get unusable, would it still operate normally due to voluntary mining?
Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.
Even though they are still somewhat negligible to miners today, transaction fees play an important role in the protocol known as Bitcoin, and will play an increasing role in the future. Just look at all the questions this SE site gets about unconfirmed transactions. Asking how the protocol works when removing all direct mining incentives is redefining the protocol in a major way. It's like asking how HTTP would work if you remove the verbs from the protocol. At that point, it's something completely different.
When you remove such a critical part of the protocol, it's difficult to replace with something that works. For example, your proposal of doing a proof-of-work on top of the last block hash as part of the transaction will effectively break the ability to use the protocol for smart contracts.
You are essentially asking what happens if you remove critical parts of Bitcoin, but still use the basic idea rather than creating a new protocol to match your paradigm of no mining rewards. To that, I can only speculate that such a system is doomed for failure.