I configured my server to not allow password authentication. Now I have a new machine in a remote location, how is it possible for me to generate an ssh key and do an ssh-copy-id to the server if the server doesn't allow password authentication?
If the new server only supports key authentication, you've jumped the gun as stated by @dr01.
Assuming your new server still allows password connections, the only "key exchange" that seems possible is this:
1) generate your key on
2) log into existing server using your already configured key
scp newuser@newmachine:/path/to/generated/pubkey ~/newuser_newmachine_pubkey
cat ~/newuser_newmachine_pubkey >> ~/.ssh/authorized_keys
This manually does the same thing that ssh-copy-id would have done, except "pulls" the key from the new box, rather than ssh-copy-id "pushing" to a remote server from the new box.
You can't. You need to authenticate somehow in order to be able to access the server (in this case, for putting your pubkey on it).
First you set up pubkey authentication and copy the pubkey to the server, then you disable password authentication.