What's the best solution to manage root password of thousands servers

I'm a system administrator. In the production environment I need to manage thousands of servers. My colleagues and I uses a central manage server and distribute its public key through other servers. So we can use this manage server to ssh to other servers.

Sometimes we need to use the root password, for example when the server is down, we need to use iLO to determine the reason.

Currently, we uses a shared root password. It's unsafe. I also looked at some single server solution like OPIE(One-time Passwords In Everything), but since we have so many servers, this is not a very good idea.

EDIT:

What I want from the password manage solution is:

1. It should be safe, so One-time Password is a great solution.
2. The password can be easily entered, sometimes we need to attach monitor to server, or with iLO as I mentioned above.
3. The solution should work even the server is offline ( without any network connection )

So it's not a very good idea to set the root password to a long-and-random string, though it's generated from some known command ( like openssl passwd ). It's hard to remember, and sometimes it's hard to generate ( without my laptop around )

You could use Puppet to push out the password change to all your servers. You would define root using the user type like so:

    user { 'root':
            ensure => present,
            password => '$1$blablah$blahblahblahblah',
    }

To generate the encrypted password:

openssl passwd -1 -salt "blah"

I'd suggest perhaps changing it every month or so---maybe using a scheme that your SAs memorized. You could also distribute it via a secure method or put it in a safe.

You could always just set a disabled password. This would prevent any network access to root, and if you boot into single user-mode most distributions will boot straight to a shell.

This probably isn't as big of a security issue as you might think it is. It is trivial to bypass the root password anyway, unless you have locked down grub with a password, pretty much anyone could simply tell grub to start bash instead of initrd.

Of course this may mean, that you should instead be figuring out how to password protect your boot-loader instead.