if you remove the 2nd field of the /etc/passwd file then users can login without any challenge. Simply attempting to login will allow them in. So something like this is probably not something you'd want to do.
root:$1$iM/2lekk$rXUAcF5fY8ddLL.B1bkH63:12242:0:99999:7:::
/etc/passwd primer

- Username: It is used when user logs in. It should be between 1 and 32 characters in length.
- Password: An x character indicates that encrypted password is stored in /etc/shadow file.
- User ID (UID): Each user must be assigned a user ID (UID). UID 0 (zero) is reserved for root and UIDs 1-99 are reserved for other predefined accounts. Further UID 100-999 are reserved by system for administrative and system accounts/groups.
- Group ID (GID): The primary group ID (stored in /etc/group file)
- User ID Info: The comment field. It allow you to add extra information about the users such as user's full name, phone number etc. This field use by finger command.
- Home directory: The absolute path to the directory the user will be in when they log in. If this directory does not exists then users directory becomes /
- Command/shell: The absolute path of a command or shell (/bin/bash). Typically, this is a shell. Please note that it does not have to be a shell.
borrowed from Understanding /etc/passwd File Format
disabling password logins
There is a subtle different between this field being blank and containing an x (:x:), and a :!: in the /etc/shadow file. This means that the account is intentionally setup to not be allowed to login, which is probably more what you're after.
/etc/shadow
root:!:15669:0:99999:7:::
The same can be done for any account, which is probably the way I would suggest you do this if you truly want to only allow ssh logins using a public/private key.
Other questions
If there are no users with passwords on a server, what exactly would happen if I were to lose my SSH key, for example? Would the server become forever unavailable since there is no way to log in on it?
No so long as you have physical access to the server, you can always gain access to the system. Will require a reboot and might be slightly difficult using a VPS but should be possible.
You typically boot the sytem into single user mode at which point you can edit the /etc/passwd & /etc/shadow files as needed.
Also, how does the sudo program behave when neither the root nor the calling user have passwords? I tried it and it didn't even ask me for a password: it just worked, since I have that user ALL=(ALL) ALL line in my sudoers file (should I change that?)
Yes without passwords using sudo becomes more difficult. There are methods to use other sources when dealing with sudo. See this U&L Q&A titled: Set sudo password differently from login one.