Linux – How to track superuser activities

I'd like to know what are the best approaches for tracking superuser activities on a Linux environment.

Specifically, I'm looking for these features:

• A) Logging keystrokes to a secured syslog server
• B) Ability to replay shell sessions (something like scriptreplay)
• C) Ideally, this should be something impossible (or quite difficult) to circumvent without having physical access to the server.

Think about this from a security / auditing perspective, in a environment where different sysadmins (or even third parties) need to be allowed to perform privileged operations on a server.

Every administrator would have his o her own nominal account, and every interactive session should be fully logged, with the possibility of replaying it if necessary (for example, if someone used mc to delete or alter critical files, it wouldn't be enough to know that that person issued the mc command; there must be a way to see exactly what was done after launching mc).

Additional notes:

1. As womble has pointed out, may be the best option would be not having people logging in with root privileges to perform changes on servers, but instead doing that through a configuration management system. So let's assume a situation where we don't have such a system and we need to grant root level access to different people over the same server.
2. I'm not interested at all in doing this surreptitiously: every person logging in to a server with root privileges would be fully aware that the session will be recorded (in the same way that, for example, call center operators know that their conversations are being recorded)
3. No one would be using a generic superuser account ("root")
4. I am aware of ttyrpld and it seems to do what I'm looking for. But before going that way, I'd like to know if this can be solved by using an unmodified kernel. I want to know if there are any tools for Debian in particular (or Linux in general) that allow full auditing of superuser accounts without patching the shell or the kernel.