Ubuntu – Root access that can’t change root password

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.