I lost access via ssh to my amazon ec2 instance and I need to access it NOW due to a problem with my service. I was told that there is a way to access the command-line via web with a java applet but I haven't been able to find it.
Is there a way to access the command-line without the .pem file? terminating/rebooting the instance is not feasible.
AFAIK it is not possible - Amazon does not retain private keys and once your instance has been assigned a keypair, it cannot be reassigned.
You could try to create a new instance with a separate keypair and ssh locally between them, but I don't imagine that that is possible.
If it's an EBS-based instance and you were able to stop it, you could mount the EBS volume to a new instance and copy a new key over; however, based on what you said, I don't believe it's possible. You may need to contact Amazon, but even then, there might not be anything that can be done.
Edit: on the same vein as the 2nd line, if you have other user accounts who have valid login shells, and you have sudo access on one of those accounts, you can do the same as mentioned in the last bit, where you generate a new keypair and upload the private key to ~/.ssh/authorized_keys.