I just usually set up an IPv6 tunnel (from sixxs.net or he.net) if they don't already have IPv6 and then that way the computer has a static address and I don't have to mess with NAT. I also like to set up key based authentication (then they don't have to tell you their password).
Sixxs has their own client that you use. It works behind almost any NAT, and automatically updates when the IPv4 address changes. They have instructions on how to set it up and it is packaged for Ubuntu.
Hurricane Electric uses a tunnel where IPv6 packages are sent as the payload of a IPv4 packet. Unlike Sixxs, no TCP/UDP is used. This means that the NAT you are behind has to support forwarding PROTOCOL 41 (not port) and only one computer behind the NAT can use it. The software to use a tunnel like this is built into Ubuntu.
For HE, I use something like this in /etc/network/interfaces
:
auto he-ipv6
iface he-ipv6 inet6 v4tunnel
endpoint 216.218.226.238
address 2001:470:a29f::2
netmask 64
ttl 64
up ip -6 route add default dev he-ipv6
down ip -6 route del default dev he-ipv6
The other thing you need to do is update your tunnel endpoint. Since you do not know when the External IP changes, you will have to just try to update the endpoint every few minutes. You could use something like this and run it from cron:
#!/bin/sh
echo -n "Hurricane Electric Proto-41 tunnel endpoint update: "
#(C) 2010 Erik B. Andersen This script is licensed under the latest version of the
# AGPL published by the Free Software Foundation at http://www.gnu.org/licenses/ .
####Set these for each different site#########
pass="passwordhere"
user_id="a765b8e2f474667dcb56e08c5f1aa05b"
tunnel_id="97817"
####Past here doesn't need to be changed######
wget -4 "https://ipv4.tunnelbroker.net/ipv4_end.php?ipv4b=AUTO&pass=$(echo -n "${pass}" | md5sum | grep -o -E "[0-9a-fA-F]{32}")&user_id=${user_id}&tunnel_id=${tunnel_id}" -O /dev/null -o /dev/null --no-check-certificate
echo " Done"