SSH - Add public keys to server after disabling PasswordAuthentication

How can I add public keys to a host from unauthorized clients after disabling PasswordAuthentication?

I have one client registered to the host via public key. I need to add additional clients. Do I need to turn on PasswordAuthentication every time I need to add a new key?

Is there a different scheme for accomplishing this task that I'm not aware of?

Don't turn on PasswordAuthentication just to add a new key. Authenticate with the key which is already authorized in order to upload the new public key. Add a new line to the authorized_keys file containing the new public key. (The authorized_keys file contains one public key per line. For example:

# Copy new public key across
scp new_key.pub server:~
# Shell into the server, again using existing key to auth
ssh server
# Append (using >>) the new public key to authorized_keys:
cat new_key.pub >> ~/.ssh/authorized_keys
# Clean up
rm new_key.pub

Now try authenticating with the private part of the new key.

However, if you've switched off PasswordAuthentication without adding any public keys in the first place, you'll need to look for another way to gain access to the server. Possibly at the physical terminal, or if it's cloud based investigate if the provider has a console login available through the control panel.