Permission Denied while Copying SSH Key for New User

When setting up a new host, you will come across the need to copy SSH keys to it.

This is easy to do, before disabling password authentication.
But, the command line gyrations to copy a public key to a remote host while simultaneously logging into it with a different key quite often fails.
So, here’s an easy means to get a key pushed to a new host:

You actually need to login to copy your key, as you don't have any access to the remote machine (invalid key and password authentication disabled):

Re-enable passwd authentication in /etc/ssh/sshd_config:

PasswordAuthentication yes

Then restart the service:

service sshd restart

Copy your public key:

ssh-copy-id -i ~/.ssh/id_rsa.pub USER@HOST -p PORT
[Enter user password]

Try to login again, no password should be required.

Then disable password authentication.