Internet Recovery should work:
http://support.apple.com/kb/HT4718
OS X Internet Recovery
If you happen to encounter a situation in which you cannot start from the Recovery System, such as your hard drive stopped responding or you installed a new hard drive without OS X installed, new Mac models introduced after public availability of OS X Lion or OS X Mountain Lion, automatically use the OS X Internet Recovery feature if the Recovery System (Command-R method above) doesn't work. OS X Internet Recovery lets you start your Mac directly from Apple's Servers. The system runs a quick test of your memory and hard drive to ensure there are no hardware issues.
OS X Internet Recovery presents a limited interface at first, with only the ability to select your preferred Wi-Fi network and, if needed, enter the WPA passphrase. Next, OS X Internet Recovery will download and start from a Recovery System image. From there, you are offered all the same utilities and functions described above.
As with the Recovery System, reinstallation of OS X Lion or OS X Mountain Lion from OS X Internet Recovery requires an Internet connection. See "Supported network configurations and protocols" below.
Some computers that did not ship with OS X Lion or OS X Mountain Lion installed may have a software update available that allows them to use Lion Internet Recovery.