Are you damned to lose all that work you have poured into that machine? Probably not, if you have the luxury of some downtime.
AWS does not have any (easy) way to just change the SSH key that can access to a system.
So after 30 minutes of attempts this is how I managed to get access back to my machine.
- Create another machine (a copy or just a new one it doesn't matter) and start it up. Pay attention to authorize a new SSH key that works to access this machine.
- Shut down the original machine
- Detach the (root) disk volume
- Attach that volume to the running instance
- mount the root partition (running dmesg or fdisk -l will tell you what to mount)
- go to <mtpoint>/root/.ssh/
- vi authorized_keys and add there the public key of your new key
- shutdown this new machine
- detach the volume
- reattach it to the old instance
- restart the instance and ssh into it with the new key
Be happy.
Ps. I found here another method involving snapshots but I just couldn't make it work. For some reason the cloned machine was always empty.