I figured out to make it work with a behind-NAT connection.
I have to connect to the server with ssh like this -
ssh -A -R 9999:localhost:22 urth.org
Now I've updated my script to assume that there's a reverse tunnel on port 9999:
use File::Temp qw(tempfile);
my ( $fh, $filename ) = tempfile();
print $fh $_ while <>;
seek $fh, 0, 0;
system( 'scp', '-P', 9999, '-o', 'StrictHostKeyChecking=no', $filename, 'localhost:' . $filename );
system( 'ssh', '-p', 9999, '-o', 'StrictHostKeyChecking=no', 'localhost', 'DISPLAY=:0.0 gnome-open ' . $filename );
I was getting lots of host key warnings, presumably because localhost is not really localhost here, it's my client machine.
This spits out some warnings, but it does the job just fine.
BTW, I love how scp uses "-P" for port and ssh uses "-p". Doh!