Lion Recovery Terminal will not allow me to run TestDisk?
Have you tried booting from a Linux LiveCD (well, instead of a CD, you'll need a USB thumb drive, but it's the same idea)? From there you could copy data to an external hard drive and just wipe the internal hard drive and reinstall.

If you have another Mac laying around with Thunderbolt, you can boot your Mac into Target Disk Mode (hold down T while booting), connect the Macs together with a Thunderbolt cable, and perform any disk recovery from there. (You might be able to go to an Apple Store and use one of their Thunderbolt Macs to recover your drive; they can be surprisingly permissive at times.)