Can I boot Linux (any distro?) from USB on a MacBook Air that has no hard drive?
I think it may be possible. I only have 2x iMac's, and I don't really want to pull the HDD out of either of them to test. However, that being said, a Mac system uses EFI rather than BIOS so you would need a Linux distro that has support for EFI.
I am a hardcore Debian user, so this would work with both Debian and Ubuntu.
Some things to decide:

Are you using 32-bit or 64-bit version of Linux?
Does your preferred version of Linux support booting from EFI?
Does the Linux distro you want have LiveCD or LiveDVD versions?


Once you have decided this, fill in the blanks with what you need:

Format a USB to Fat32 with MBR record
Create /efi/boot directory on this drive
Download either the 32-bit EFI or 64-bit EFI file and put it in the /efi/boot directory
Download the LiveCD or LiveDVD version of the Linux OS you want to run
Move the ISO file to the /efi/boot directory and rename it to boot.iso


Reboot your Mac with the USB in and hold down Alt/Option key when booting and you should be presented with a USB drive to select to boot from.