If you're worried about speed you could try to find a small SSD (and/or look for USB3, there are some cheapo usb3 drives out there. I don't know if the flash storage is fast enough to matter though.)
To get it to boot, all you really need to do is make sure that you use GRUB2 and do an EFI install to the external SSD. (Ubuntu will do this automatically, as will Fedora and no doubt others). (I want to say that rEFIt would handle this no matter what, but I can't remember even with my own MBA when USB will work with the EFI->BIOS bridge.
To get it to boot, all you really need to do is make sure that you use GRUB2 and do an EFI install to the external SSD. (Ubuntu will do this automatically, as will Fedora and no doubt others). (I want to say that rEFIt would handle this no matter what, but I can't remember even with my own MBA when USB will work with the EFI->BIOS bridge.