How can I create a Lion USB recovery stick without Mac OS?
I've heard rumblings that the Lion Recovery Update will recreate the Recovery HD partition. Have not tested it myself: http://support.apple.com/kb/DL1464 (For future reference, does little to help you now).

But to address your immediate problem, install Snow Leopard (using the discs that came with your Mac). Then once installed, log into the MAS and reinstall Lion.