It might not be brilliant, but it works. Just reinstall Snow Leopard and you can download Lion again for free from the Mac App Store with your Apple I.D. Makes sense to me...
In the developer preview, the way to do a clean install (that I've used for every developer preview) is to create a blank partition, formatted as HFS+, and tell the installer to install Lion there.
You only have to do it once, because once Lion is installed, it will put a recovery partition on the hard disk. So you won't need a disc after the initial install.
OS X Lion includes a built-in restore partition, allowing you to repair or reinstall OS X without the need for discs.
Slow connection?
Maybe I'm missing something, but wouldn't the definition of a clean install rule out installing Snow Leopard and the upgrade to Lion? A clean install, in my mind, means installing the OS from scratch on your new system/drive.
The only way they will distribute it is through the AppStore so you need at least Snow Leopard to do that. Once you have a copy you can burn the DMG to a dvd (or usb stick) and boot that directly on any core2duo or better mac