I tried Ubuntu 8.04 Beta yesterday. Easy to install, but you have to do few tricks to get wireless working. Touchpad didn't feel too good under Linux, but you can probably adjust it later.
Just use Bootcamp, but instead of putting in a Windows cd use Ubuntu.
Google for instructions. "installing" "Ubuntu" and "MacBook Air" should be good keywords.