The host key is generated on first boot of any instance. Init scripts are run at every boot that access the machine instance data. The initscript saves the instance id in a particular file: this way, if the file is absent or contains a different ID, the system initialization stuff is run.
That includes generating the host key (stored at /etc/ssh/ssh_host_{rsa,dsa}_key), downloading the user public key from the metadata and storing it in the authorized_keys file, setting the hostname, and performing any other system-specific initialization.
Since the determining factor is not the hard disk, but the (unique to each instance) instance ID, these things will always be done when you boot EBS volume attached to a new instance.
Edit:
I looked deeper into Ubuntu specifically and installed an ubuntu ami (3ffb3f56). I'm not a big ubuntu guy (usually prefer debian) so this was getting a little deeper into the ubuntu upstart-based init sequence than I usually go. It seems what you're looking at are /etc/init/cloud*.conf. These run /usr/bin/cloud-init and friends, which have lines like
cloud.sem_and_run("set_defaults", "once-per-instance",
set_defaults,[ cloud ],False)
All the code's in python, so it's pretty readable. The base is provided by the package cloud-init and the backend for the scripts is provided by cloud-tools. You could look and see how it determines "once-per-instance" and trick it that way, or work around your problem with some other solution. Best of luck!
The only fastest way is that which you have mentioned already, that make a small ami and host a static maintenance page on it, by attaching elastic IP to it.
There is no hard and fast rule that which AMI should be used in this scenario. Any micro instance of Debian/RHEL/Ubuntu would work fine.
Best Answer
There is no definite answer to this because that's dependent on EC2's current load. You may also experience capacity issues. In my experience I get EC2 startups in about a minute to three for a Small in west-1b. I don't think Amazon even has an SLA to guarantee the ability to start new instances. Rackspace Cloud Server 256MB is also about a minute but I've seen about three minutes or so.