Assuming for simplicity that you have only one client (but which can have arbitrary IP's), that the VNC server runs behind a firewall where you can't open ports, but the client has no such problems, a workaround would be to do put this command into an on-boot script on the server:
while sleep 100; do ssh vnc_user@$client -R 5900:127.0.0.1:5900; done
This opens a reverse tunnel from the server to the client. This is possible from behind a firewall.
Ensure you've created a passphraseless ssh-key on the server (
ssh-keygen, and press return a couple times) so you can put this in a boot script.
Now, in order to do this from an "arbitrary internet connection", simply get a free account at dyndns.org, and exchange $client in the above command for that dyndns address (e.g. myvpnclient.dyndsn.org). On the client, run sshd, and create a user with very little access:
sudo useradd -m -s /bin/false vnc_user
Copy the file server:~/.ssh/id_rsa.pub into client:~vnc_user/.ssh/authorized_keys so that the vnc server has ssh access to the vnc client(s). (The /bin/false ensures the vnc server can't actually run commands on the client, only open a port; if you don't trust the server you can do more hardening in sshd_config.)
Now as long as you run a dyndns daemon on the client (or update your IP address manually at dyndns.org), you can connect to the server. If your client changes IP address, the ssh connection should drop and the server will try reestablishing the connection.
(If the client too is behind a firewall, I guess both client and server could open tunnels to a third machine which has no firewall trouble, but in any case you need at least one server which can run sshd against the open Internet.)