Would content-aware fill be enough? http://blogs.adobe.com/jnack/2010/03/caf_in_ps.html

That's so amazing my brain won't stop screaming "FAKE!". :)