Root access that can't change root password?

This is practically impossible. First of all, if you grant them the power of becoming root, then there's nothing you can do to prevent them from doing anything. In your use case, sudo should be used to grant your users some root powers while restricting others without allowing them to become root.

In your scenario, you would need to restrict access to the su and passwd commands and open access to pretty much everything else. The problem is, there's nothing you can do to prevent your users from editing /etc/shadow (or /etc/sudoers for that matter) directly and dropping in a replacement root password to hijack root. And this is just the most straightforward "attack" scenario possible. Sudoers with unrestricted power except for one or two commands can work around the restrictions to hijack full root access.

The only solution, as suggested by SHW in the comments is to use sudo to grant your users access to a restricted set of commands instead.

---

Update

There might be a way to accomplish this if you use Kerberos tickets for authentication. Read this document explaining the use of the .k5login file.

I quote the relevant parts:

Suppose the user alice had a .k5login file in her home directory containing the following line:
[email protected]
This would allow bob to use Kerberos network applications, such as ssh(1), to access alice‘s account, using bob‘s Kerberos tickets.
...
Note that because bob retains the Kerberos tickets for his own principal, [email protected], he would not have any of the privileges that require alice‘s tickets, such as root access to any of the site’s hosts, or the ability to change alice‘s password.

I might be mistaken, though. I'm still wading through the documentation and have yet to try Kerberos out for myself.

We want that some users should be able to do e.g. sudo and become root,

Well, that's the problem sudo is designed to solve, so that part is easy enough.

but with the restriction that the user can't change root password.

You can, as SHW pointed out in a comment, configure sudo to only allow certain actions to be taken as root by certain users. That is, you can allow user1 to do sudo services apache2 restart, allow user2 to do sudo reboot but nothing else, while allowing the hired-as-system-administrator user3 to do sudo -i. There are howtos available on how to set up sudo like that, or you can search (or ask) here. That is a solvable problem.

However, a user that has been granted the ability to sudo -i or sudo into a shell (sudo bash, for example) can do anything. That is because by the time sudo launches the shell, sudo itself is out of the picture. It provides the security context of a different user (most often root), but has no say in what the executed application does. If that application in turn launches passwd root there is nothing sudo can do about it. Note that this can be done through other applications, too; for example, many of the more advanced editors provide facilities to execute a command through the shell, a shell which will be executed with the effective uid of that editor process (that is, root).

That is, a guarantee that we still can login to that server and become root no matter of what the other users will do.

Sorry; if you really do mean "ensure we'll be able to log in and use the system no matter what someone with root access does to it", that (for all intents and purposes) cannot be done. A quick "sudo rm /etc/passwd" or "sudo chmod -x /bin/bash" (or whatever shell root uses) and you are pretty much hosed anyway. "Pretty much hosed" meaning "you'll need to restore from backup and hope they didn't do anything worse than a slip of fingers". You can take some steps to reduce the risk of an accidental mishap leading to an unusable system, but you cannot prevent malice from causing very serious problems up to and including the point of needing to rebuild the system from scratch or at the very least from known good backups.

By giving unfettered root access on a system to a user, you trust that user (including any software they might choose to execute, even something as mundane as ls) to not have malicious intent, and to not mess up by accident. That's the nature of root access.

Limited root access through e.g. sudo is a bit better, but you still have to be careful to not open up any attack vectors. And with root access, there are plenty of possible attack vectors for privilege escalation attacks.

If you can't trust them with the level of access that being root entails, you'll need either a very tightened down sudo configuration, or to simply not grant the user in question root access at all through any means, sudo or otherwise.

I'm assuming you want to make sure you have an "emergency admin" access, even if your actual administrator screws up (but other than that, you trust the main administrator fully).

A popular approach (although very hackish) is to have a second user with uid=0, commonly named toor (root backwards). It has a different password, and can serve as a backup access. To add, you'll likely need to edit /etc/passwd and /etc/shadow (copy the root lines).

It's all but fail-safe, but if you just need to safeguard against the "main administrator" changing the password without notice, then it will work. It's trivial to disable, by removing the toor account; so the sole benefit is having a separate password.

Alternatively, you may want to look into alternate authentication mechanisms, i.e. ssh keys, libnss-extrausers, LDAP etc.

Note that the admin can still screw up badly. For example, by blocking the firewall.

If you want to have a very secure system, consider using SELinux, where the unix user (e.g. root) is also coming with a role, which can be much more fine grained. You may want to give your admin root access, but only a restricted role (e.g. to administrate apache only). But this will require quite a lot of effort on your side to correctly configure the policy.