If you need to access that specific instance there is possibly a workaround to your situation. You will need access to the AWS Web Console and the instance will need to be a EBS backend instance. What you will need to do is;
- Stop the running instance. (Do Not Terminate it, just shut it down for now)
- De-attach the EBS backend from the instance
- Create a new EC2 instance.
- On new system, create a mount point /mnt/oldsystem
- Attach EBS backend from old instance to the new instance and mount it as /mnt/oldsystem
You should now have access to the file system of the old instance. Navigate the the user account you want to log in as, assuming ubuntu from your post, and add your new ssh key to the .ssh/authorized_keys file (path should be /mnt/oldsystem/home/ubuntu/.ssh/authorized_keys)
Once you are done, unmount /mnt/oldsystem and de-attach the EBS backend. Now you can re-attach the EBS to your original instance, start the instance up, and you should be able to use your SSH key to log into the account now.