Then have a bastion host in a DMZ that forward to the actual instances (I prefer 172 as it tends to avoid clashing with wifi networks). This does cost you a m1.small Amazon instance, but if you reserve it the cost is negligible.
Even better. You can do this automagically with ssh by putting a suitable `ProxyCommand ssh <bastion> "nc %h %p"` in your ssh config. So you just `ssh 172.0.0.10` or ssh `my-internal-name.blah` and it tunnels straight in for you.
You can pair this with internal DNS if you want to get really fancy - although it's a bit fiddly. From what I read internal DNS is pretty high up on the Route 53 feature request list.