You should have Internet recovery then and can go back to Lion. Did you try the command-option-r boot? That should get you to a spinning globe and in a couple minutes you will see the recovery screen. Start Disk Util and select the drive brand name (like Seagate 500GB or whatever) and erase to Mac OS Extended. By erasing the entire drive instead of just Macintosh HD you will get rid of the Mt. Lion recovery partition and allow the installer to install Lion.
Once you get done with the erase, quit Disk Util then click install OS. That will give you a free DL of Lion (tied to the machine's serial number) with no AppleID required.
This will get you up and running with the original Lion install. From there, if you like, you can go to the App Store and buy Mt. Lion for yourself.