Is it possible to to do add a brand new SSD to a MacBook Pro and just fresh install Lion?
Yes. Hold the &#x2325; key while booting up to select your install USB.

Also note that if you upgrade to the most recent version of Lion you should get the recovery partition to boot up without having to use the USB (internet connection required).