In a thread on the EC2 forum, Marko describes a situation where an outbound firewall prevents the ability to ssh to port 22, which is the default port on all EC2 instances.
In that thread, Shlomo Swidler proposes creating a user-data script that changes sshd to listen on a port the firewall permits.
Here’s a simple example of a user-data script that does just that. Most outbound firewalls allow traffic to port 80 (web/HTTP), so I use it in this example.
The first step is to create a file containing the user-data script:
cat <<'EOM' >user-data-ssh-port-80.txt
#!/bin/bash -ex
perl -pi -e 's/^#?Port 22$/Port 80/' /etc/ssh/sshd_config
service sshd restart || service ssh restart
EOM
The first statement changes the sshd config to listen on port 80 instead of port 22, and the second statement restarts sshd so it will start using this new configuration.
Now you can run a new instance on Amazon EC2, passing in this user-data script. Since the AWS APIs use standard web ports, most outbound firewalls will let through these types of requests. In this example, I use a 64-bit Ubuntu 10.04 Lucid AMI from Canonical which was current as of this article. Please use the most recent AMIs available.
ec2-run-instances --key YOURKEYPAIR --region us-east-1 --instance-type t1.micro --user-data-file user-data-ssh-port-80.txt ami-4a0df923
Save the instance id created and make a note of the IP address once it starts. Now you can ssh in to port 80 using the keypair you specified:
ssh -p 80 -i YOURKEYPAIR.pem ubuntu@IPADDRESS
If you don’t get through right away, make sure your EC2 security group allows access on port 80, and wait long enough for the instance to boot. If you’re connecting to an Amazon Linux AMI, ssh to ec2-user@ instead.
To avoid having to include “-i YOURKEYPAIR.pem” in every ssh, upload your personal ssh key to EC2.
After testing this, don’t forget to terminate your EC2 instance.
See also: Escaping Restrictive/Untrusted Networks with OpenVPN on EC2
Disclaimer
These instructions are not intended to assist in illegal activities. If you are breaking the laws or rules of your government or college or company or ISP, then you should understand the implications and be willing to accept consequences of your actions.
[Update 2010-12-06: Enhanced user-data script to work on both Ubuntu 10.04+ and Amazon Linux (CentOS). Updated AMI id.]


The suggested '/etc/init.d/ssh restart' will probably work, but is not the correct method for managing the ssh daemon.
Instead, you *should* use:
restart ssh
or
service restart ssh
This is "transition to upstart" point.
smoser: Thanks. I had been trying to write a user-data script that could be portable across some Linux distros, but on testing it wasn't. I just updated the steps to both use the newer format (service ssh restart) and tweaked it to also work on an Amazon Linux AMI (service sshd restart). Amazon Linux also has the "Port 22" commented out which I now account for.
Shirley, it's better to use 443 instead of 80. Proxies and firewalls don't try to interfere with SSL, because they can't. But they can and do play games with HTTP.
rev.chip: Good point, thanks.