There is no real safe way of doing it.
With a hard fork, getting consensus first is important.
The problem is how to handle it if complete consensus isn't achievable. The 95% rule with soft forks recognises that getting everyone to agree is to high a standard, but it still requires near total agreement.
It is pretty clear that complete consensus isn't required, even for hard forks. If 95% of miners and 95% of merchants updated, then everyone else would have to update too.
Of course, I could be wrong about all this. Also, as you pointed out, any BIP that doesn't require a fork can be implemented at any time. For example, BIP 32 is pretty widespread now, and that one didn't require a fork.
I think giving notice is the best bet. If 95% of the miners say that "starting with block 400,000 we will be using larger blocks", then that gives notice to everyone else to update.
Satoshi could have made the 1MB "anti-DOS" rule expire and I don't think anyone would have objected.
The suggestion on the mailing list is to look at the client names in the version message. If most nodes end up using the large-block version of the client, then that shows that there is wide support for larger blocks. It wouldn't be an automatic thing, but a way to show that there is consensus for larger blocks.
The large block debate could set the rules for how to handle hard forks that don't have complete agreement.