I had a machine crash, and needed to setup another one with SSH access. I got the console login ok, but no way to paste my public key there. Just spent a whole day trying to find a way to do this.
My solution, finally was to put the public key on a public dropbox folder, then in the console, use:
curl 'https://dl.dropbox.....' > temp1
cat temp1 >> .ssh/authorized_keys