Was für ein MacBook Air ist es denn? Hast du ein externes Laufwerk? Hast du eine Installations-DVD oder einen USB Stick mit Mac OS X Lion installiert?
Hast du die komplette Festplatte neu partitioniert und damit die Recovery-Partition gelöscht?
Starte den Mac mal neu und drücke cmd + R während des Starts. Wenn das geht, kannst du so neu installieren.
(Ich gehe davon aus, dass du kein Backup hast, sonst könntest du das einfach wieder einspielen.)