Which Time Machine backup destination over Wi-Fi to choose: old computer running Ubuntu or Time Capsule?
Both are feasible. I use the first myself, and my sister had the second set up at one point.

1) On the laptop, you can install netatalk which handles AFP file sharing. Time Machine requires some special AFP features but those are supported by the version of netatalk that comes with Ubuntu 12.04 (just do sudo apt-get install netatalk).

Here's a decent guide for that, although with current versions you shouldn't actually need avahi-daemon, netatalk can handle Bonjour by itself now. You may actually just be able to get away with adding a line like:

/home/username/backup    "Time Machine"  allow:username   options:tm,noadouble


to /etc/init.d/netatalk/AppleVolumes.default, which is all I had to do on one machine running 12.04 (I don't remember having to do the other stuff, but YMMV).

Note that you should NOT ever need to use the "EnableUnsupportedVolumes" hack as netatalk meets Apple's spec and should appear as a backup destination automatically. Using this hack causes Time Machine to ignore problems that can cause loss of your backups.

2) A Time Capsule can indeed be connected to a wireless network as a client to share the hard drive (it can also share a printer connected via USB). I think the setup wizard makes it pretty easy, you're basically just looking to set it up as a wireless client and not a router. You might want to hook it up by ethernet if the signal isn't so great, though.

If 320GB is enough space (which I imagine it is, unless your Air has a 512GB SSD), I'd go with the netatalk solution unless money is no object.