I think the New Zealand experience is an extremely interesting one. In the case of New Zealand, it happened in spite of the opposition of the two main parties that had been the beneficiary of the previous FPTP system. In some ways you can say that in New Zealand it happened by accident. In fact, the two major parties tried to scuttle the change to PR, and it only happened because there was a strong popular movement that demanded a referendum. Reluctantly the governing party allowed that referendum, but it still tried to structure it in such a way that the outcome might be the defeat of PR. As you said, there were three referendums, one on which of the alternative methods should be chosen. The winner of that was placed against the FPTP system.
I think the reason it took such a long time in New Zealand was that the political establishment was against it. I think a better way to do this is for the representatives of the people in parliaments, as in your House of Commons, to discuss it and not have to push it through against the wishes of the major traditional players.