Add Keypair to existing EC2 instance

https://forums.aws.amazon.com/thread.jspa?threadID=46776&tstart=45#179656

1. Launch a new instance
2. Detach root device from locked instance (must be EBS)
3. Attach root device for locked instance to new instance
4. Logon to new instance, mount attached device, replace .ssh/authorized_keys with that of the new instance (or whatever)
5. Unmount, detach, reattach

Just to provide another option in case somebody reads this: If the instances are managed via some kind of configuration management system, like Puppet or Chef, you can use that to push new keys to the running instance.

Unless the AMIs used have a "backdoor" (which you can add on custom AMIs but is definitely not a good idea security wise and by backdoor I mean a pre-set private key and/or password authentication enabled) you're stuck unless you have the PK for the keypair used on those instances. Your only choice is to start-up new instances with a new keypair.

Sorry I couldn't give you the answer you wanted.