I like all these strategies, but I simply have to ask the question: Where is the big security faux-paus in ssh as root to a machine? I'm not trying to be antagonistic, I really want to understand this. Let me setup the situation in a little more detail.
1) Do not use keys for authorization. I still use a password authentication for ssh. I'm just using ssh for an encrypted connection (no keystroke monitoring and such).
2) Have a good host.allow and host.deny setup regardless.
3) All activitiy is happening behind a pretty good firewall.
Are you simply saying that you should never have the ability to login as root on any machine? I don't see the difference between a hacker accessing one of your machines because a user has poor password techniques and then getting lucky and figuring out roots amazing password and switching to root.

He can also ssh to another machine that may have the same bad user, logging in as that user and hope that root set his password the same (which this root doesn't). Again, I'm not being antagonistic, I just want to know the issue here. Thanks a bunch. All the best....