Start with a machine that is directly accessible to both parties via SSH (linode, EC2, prgmr.com, etc), and that you can add users to. DO NOT USE root!!!!
##From the hosts local machine:
ssh -R1337:localhost:22 host@<shared server's ip address/hostname>