A remote client is behind a firewall and the firewall is configured to allow outgoing access only and to only allow outgoing access to a single IP which is myserver.com.

The remote client executes the following:

ssh -R 2222:localhost:22 someuser@myserver.com

Then on myserver.com, the following can be executed to create a ssh tunnel into the remote client:

ssh -p 2222 someuser@localhost

That is, until I accidentally deleted all the keys in myserver's /home/someuser/.ssh/authorized_keys

Is it possible to configure myserver to allow user someuser to ssh into myserver without a password or ssh key?

Is it possible to retreive the remote client's public key when it attempts to connect?

ssh-copy-id attempts to add the file ~/.ssh/id_rsa.pub to the authorized_keys file on a remote host. You could enable password login long enough to do this, or you can copy the file manually and append it to authorized_keys. I don't know an easy way to capture it out of the ssh handshake (except maybe using wireshark).

Either way I have to gain physical access to the machine. Which is possible, just a pain. I am starting to think there public key is never passed upon initial connection attempt, only its key because presumably it already exists on the remote server.

Except for the ssh-copy-id command the actual keys are never sent between the client and the server during a ssh session.

You can enable the server for password authentication and you can allow empty passwords but the later is highly discouraged. If the public key still exists on the remote server you will either need to gain physical access or have someone send you the key in some other manner.

If the public key does not exist on the remote server you will need to generate new keys.

Or might as well generate new keys, it can be a good opportunity to rotate keys. Though if the private keys are still available on the client the public keys can be regenerated easily with ssh-keygen

Yep, forgot about that..

I usually do to. It has come in handy about twice so far though.

If you want "neither passwords nor an ssh-key," just use telnet.

Seriously.

An SSH connection provides no(!) more actual security than telnet, if it is possible for anyone in the world to get to a login: prompt.

If you want to secure the connection without inconveniencing your users, simply use an OpenVPN tunnel, secured by tls-auth and unique digital keys. The users on both sides will find that "the other side is 'part of our local network.'" And yet, communication between the two is provably secure, and the identity of the party on the far side of the link can be relied-upon. Although the encryption process is now made entirely invisible to authorized users, it is there.

And, with tls-auth, it is invisible to the outside world: there are no "open ports," and attempts to start an OpenVPN connection are ... silently ignored. Authorized users pass swiftly through. L33T H4X0RZ cannot detect that the secret door exists.

"Number of unauthorized connection attempts: Zero."