Ubuntu – Recovering from ‘sudo rm -rf –no-preserve-root /’ Mistake

Please note: The answers and comments to this question contains content from another, similar question that has received a lot of attention from outside media but turned out to be hoax question in some kind of viral marketing scheme. As we don't allow ServerFault to be abused in such a way, the original question has been deleted and the answers merged with this question.

Here's a an entertaining tragedy. This morning I was doing a bit of maintenance on my production server, when I mistakenly executed the following command:

sudo rm -rf --no-preserve-root /mnt/hetznerbackup /

I didn't spot the last space before / and a few seconds later, when warnings was flooding my command line, I realised that I had just hit the self-destruct button. Here's a bit of what burned into my eyes:

rm: cannot remove `/mnt/hetznerbackup': Is a directory
rm: cannot remove `/sys/fs/ecryptfs/version': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/inode_readahead_blks': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/mb_max_to_scan': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/delayed_allocation_blocks': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/max_writeback_mb_bump': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/mb_stream_req': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/mb_min_to_scan': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/mb_stats': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/trigger_fs_error': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/session_write_kbytes': Operation not permitted
rm: cannot remove `/sys/fs/ext4/md2/lifetime_write_kbytes': Operation not permitted
# and so on..

I stopped the task and was relieved when I discovered that the production service was still running. Sadly, the server no longer accept my public key or password for any user via SSH.

How would you move forward from here? I'll swim an ocean of barbed wire to get that SSH-access back.

The server is running Ubuntu-12.04 and hosted at Hetzner.