For the most part, this is the same as any post about creating an image for Eucalyptus, but I had a hard time figuring out exactly how to put it all together. You need an up to date Debian sid system nearby to take the kernel and ramdisk from. I found having a sid VM easier than discovering the commands to build a sid initrd on my Ubuntu workstation.

# First, the prerequisites. You need debootstrap and the eucalyptools tools installed.
sudo apt-get install debootstrap euca2ools

# Export your eucalyptus variables to use the tools.
source ~/.euca/eucarc

# Create an empty disk image. You can adjust the count to change the root disk size. 1000 is about a GB.
dd if=/dev/zero of=image count=1000 bs=1M

# Put a filesystem on the new disk image
mkfs.ext3 -F image

# Mount the filesystem
mkdir chroot
sudo mount -o loop image chroot

# Install debian sid to the chroot. Notice that the ssh server and curl are included here
sudo debootstrap --include=openssh-server,curl,vim --arch amd64 sid chroot/ http://ftp.debian.org

# chroot into the image
sudo chroot chroot

# Setup basic networking and disk configurations
echo -e 'auto lo\niface lo inet loopback\nauto eth0\niface eth0 inet dhcp' >> /etc/network/interfaces
echo -e '/dev/sda1 / ext3 defaults 0 1\n/dev/sda2 swap swap defaults 0 0' > /etc/fstab

# Set a default root password if you want
# passwd

# Set up the image to automatically install ssh keys
mkdir /root/.ssh
cat <<EOS > /etc/rc.local
echo >> /root/.ssh/authorized_keys
curl -m 10 -s http://169.254.169.254/latest/meta-data/public-keys/0/openssh-key | grep 'ssh-rsa' >> /root/.ssh/authorized_keys
echo "AUTHORIZED_KEYS:"
echo "************************"
cat /root/.ssh/authorized_keys
echo "************************"
exit 0
EOS

# Leave the image
exit

# Unmount the image
sudo umount chroot

# After you've copied the latest /boot/vmlinuz* and /boot/initrd* from your sid system, upload the kernel + ramdisk
euca-bundle-image --image vmlinuz-2.6.38-2-amd64 --kernel true
euca-upload-bundle --bucket sid --manifest vmlinuz-2.6.38-2-amd64.manifest.xml
euca-register sid/vmlinuz-2.6.38-2-amd64.manifest.xml
euca-bundle-image --image initrd.img-2.6.38-2-amd64 --ramdisk true
euca-upload-bundle --bucket sid --manifest initrd.img-2.6.38-2-amd64.manifest.xml 
euca-register sid/initrd.img-2.6.38-2-amd64.manifest.xml

# Prepare the image for upload, use the values given by euca-register above here
euca-bundle-image -i image --kernel eki-XXXXXXXX --ramdisk eri-XXXXXXXX

# Rename to manifest to something descriptive and upload it
mv image.manifest.xml `date +%Y%m%d`.sid.manifest.xml
euca-upload-bundle -b sid -m `date +%Y%m%d`.sid.manifest.xml

# Register the image to get an EMI
euca-register sid/`date +%Y%m%d`.sid.manifest.xml

You should be able to use euca-run-instance on the emi that is returned by the last command. Remember to pass an ssh key (that eucalyptus knows about) using -k. If there are any issues, use euca-get-console-output to monitor the instance startup and tail the eucalyptus/nc.log file on the node controller for any errors. Building the initrd this way is a little hackish, because it is actually generated for your sid system, not for the one running in eucalyptus. Chicken, or the egg?