You can show up with a blank drive, that probably won't be a problem. You can go through the purchase process at the Apple store on one of their machines and then one of the Geniuses should pretty much do the install for you.

Lion was also available for purchase on USB thumb drive, but I don't know if the store would still have any of those around. If so, then should be as simple as booting off that USB stick and installing the same way you would from a DVD.