Installed new SSD, but I have no Snow Leopard disk. Can I install Lion from Internet? I've just installed a 128GB SSD onto my 2009 MacBook Pro. I've run into an issue.

I was under the impression you can install Lion over the Internet on a fresh install. I've done this before on a family members MacBook. I can't replicate it though. I have purchased a copy of Lion, and I installed it on the old drive.

I do not have a copy of Snow Leopard as I gave it away by mistake when I sold my iMac. Gave the guy the wrong disk.

I no longer have the old HDD contents, and the only other computer I have in the house to download anything to is a computer without an optic disk drive - a Macbook Air.

What are my options for installing OSX on the MBP with the new SSD?

I am sure I was able to install Lion over the web on my stepdads MacBook on a fresh install as he has no Snow Leopard installation disk.

Any advice is much appreciated. At the moment I am seeing a folder with a question mark at boot, which I understand is usual behaviour as there is no OS.
Lion / Mountain Lion's recovery is only present on hard drives that have the system already installed.  Internet Recovery (likely what was used with your Dad's Mac) is only built in to newer systems that shipped with Lion or Mountain Lion. Apple support page documenting this

In your situation I think your best bet would be to download Mountain Lion using your MacBook Air, build a Mountain Lion installer disk using the application below, boot to the install disk/drive by holding option while powering on your Mac and selecting the disk and installing as usual from there.

Lion Disk Maker

Hope that helps!