I'm setting up a server which other people will have sudo access to via ssh. They can install stuff and make changes as they see fit, however I still need to manage the server, install patches and software updates etc.
I'm wondering if I keep the root password so that I can always do what I need to, can I somehow disable people with sudo from being able to change it with sudo.
You can selectively allow certain commands with sudo, but you must be careful to not permit programs that allow shell access, writing to sym links, or one of a few dozen other problems. Here's a page on secure sudo scripting: http://www.kramse.dk/projects/unix/security-sudo-script_en.html
You could always hope that they don't know about the chattr command ;-)
You have to think about it like this. If you give them the root password, or a route to it, you're essentially asking "how can I give them root except for all the times when I magically don't want them to have it". And the answer is "you can't. Computers don't work that way."
I think the answer here depends on whether you are trying to stop them from maliciously changing the password to keep you out, or just carelessly getting the password because they forgot you need access. In the former case you are going to have a lot of trouble. I don't know under what circumstance you would give users root access to the box but still be worried about this, but the best you can do is try to limit their access to commands through sudo, which as others mentioned is tricky at best. In the latter case it seems like the solution would be to create yourself a user with sudo privileges. No one is going to accidentally change the password on your account so you don't have to worry about someone just making a mistake, or even changing the password for a good reason and forgetting to tell you about it because you can always get in with your account and change it back.
SELinux can do what you're looking for, although it's like using a nuclear-powered planet-smashing battleax to swat a fly, or whatever the Hitchhiker's quote actually is. If you're set on Linux rather than Solaris (and its shiny RBAC), the easiest-to-implement option will likely to be to configure sudo to only allow the commands necessary.
There are a few options:
As others have pointed out, giving root access will allow them to do absolutely what ever they like on the system and if they really want to lock you out; they can. The options above however make it harder or less transparent to them.
Solaris has solved this by making root as a "role" so nobody has a root password and root user cannot log in to system. To prevent anyone from locking you out, there are lots of fine grained security options; so you can have them do most of the root things with "pfexec" (equivalent of sudo) but you can be able to prevent them from revoking your sudo priviledges.
[[ I'm not a solaris fan, but there are some very good things in solaris other than ZFS and DTrace. Too bad If oracle extinguishes the flame ]]
Instead of preventing them from changing the password, just make it a policy that they are not permitted to do so. Then you can set up something like auditd to watch the password file and notify you of changes.
What you want isn't reasonable. Giving root to people in any form will allow them to wreck your system. Even if their access is via heavily regulated sudo, a clever or malicious or really deranged idiot will be able to cause mayhem.
You either trust them or you don't.
If you're supporting their needs and the firm as paying you to support them, it is their machine, not yours; you're only there to keep it working despite whatever foolish things they do. Maybe after they roast it a couple times you can ask your boss if you can give the clients less access or otherwise the firm will have to keep paying you to fix the mess. Whatever -- it's their dime.
If it is your computer and you're doing these others a favor, ask them politely to be nice.
That said -- you can always boot from CD (or other read-only media). They'll still be able to wipe out the other filesystems or mount over /etc with their own /etc, but all you need to do to get the system back to some rudimentary level of functionality.
You can also use something like openvz and give each user their own instance. They won't be able to wipe out the whole system and they'll be able to install their own software in their slice. Lots of places use this for web hosting where they give the clients "root" in the VZ slice.
If you can't use a system with RBAC, like Solaris, HP-UX or AIX, you can implement RBAC on Linux with the grsec patch.
That's where a middle-layer access user type come in need. I think if a user type would exists with customizable privileges (standard access plus some of the root accesses) it would be nice. Also to prevent this user from changing for example password file (as the linux is based on files) we could restrict the password file access permissions for not being available to that user. then put a password for BIOS to prevent user from changing /etc/shadow file with a third-party bootable flash or CD.
The above is just a theory for linux developers and not sure if it's possible...