FWIW, I recently had to do a reinstall of Lion using the Recovery HD partition and what it does is ask for your Apple ID log-in credentials and verifies it just before it re-downloads Lion, so you'll have to have had purchased it using your Apple ID prior to going ahead with a reload. At least that's been my experience when I did this last week.
What model Air? I believe that is required on ones who had SL but not Lion from the factory. My Lion laptops have not required an iTunes account to restore.
Exactly, as stated above, you will need the apple i.d. and password to redownload OSX from the app store.