An alternative to hamachi is n2n, which is in standard debian, or from http://www.ntop.org/n2n/

It works a bit like hamachi, the difference (in addition to being open source) is that you don't rely on some 3party company server to negotiate the vpn connection for you. Instead you do it yourself.

That means, of course, that you need access to an internet-exposed server that can run your 'supernode'. The supernode does not transport any of your traffic, it only makes it possible for your p2p vpn clients to reach each other through udp.
It's quite simple to compile and install for just about anything.