Can't you use a .Mac account to access your other machine on Back to My Mac? Then just connect to .Mac and play your songs that way. Not sure if you have a .Mac account but they aren't that much - $99 / year. If you have that and an internet connection, you should be good to go. Admittedly I haven't ever tried it but it should work in theory.
If you are on the same network as your main computer (at home etc) then you might be able to use iSync to sync the playlists you want to your MBA and just play those.
Another option is a small, portable HD that you can take with you, like an WD Passport. I think a 250GB Passport is about $130.
If those or some of the other options that folks posted above don't work, then you might be SOL. I would love to have a great solution to this as well, but the fact is the HD for an AIR is small, there is no other way to put it.