Once you've lost the PEM file, and it's properly gone, you're kinda screwed. You'd need to know either a password, or have another key on the server.
You need to protect those PEM files like they're your children, otherwise you effectively get locked out of your EC2 instances.
If it's an EBS-backed instance, you might be able to follow this theoretical process:
- Stop the instance you lost the key to.
- Create a new keypair
- create a new micro instance with the new keypair
- Mount the stopped instance's EBS volume
- Add the new private key from the Micro instance to the EBS volume.
- Sync and Unmount the EBS volume
- Remount / restart the lost instance.
- Connect with the new keypair.
If you've not got EBS instances, you're SOL.