How to share the internet connection?

Gentoo Linux has a very nice Home Router Guide in it's Gentoo Linux Documentation: http://www.gentoo.org/doc/en/home-router-howto.xml

Many of the steps can be adapted to use with Ubuntu.

Note: This is from my own, very small home network, and I'm not a network guy. I don't understand much of why it works and will remove this post soon, if a better one occurs. Just in case it takes some time, this might be a start, but without anything about VPN.

I'm not sure whether I know what you know, and what you are searching for.

I think you have a pppoe-connection, dns-server up, dhcp up and running.

You just need to know how to do the forwarding, and the VPN-stuff? I don't know about the VPN.

After connecting pppoe, start this in the init-process or network-ifup:

#!/bin/bash
# test if ip-forward is up - if not, enable it:
#
ipf=$(cat /proc/sys/net/ipv4/ip_forward)
if [[ ipf -eq "0" ]] ; then 
    echo "1" > /proc/sys/net/ipv4/ip_forward
fi
#
# forward-masquerade
#
. /etc/ppp/masquerade
#
# start dhcp-server now

The /etc/ppp/masquerade could look like this:

iptables -t nat -A POSTROUTING -o ppp0 -j MASQUERADE
#
modprobe ip_conntrack_ftp
modprobe ip_nat_ftp
#
iptables -A FORWARD -p tcp --tcp-flags SYN,RST, SYN -j TCPMSS --clamp-mss-to-pmtu

If the clients specify the server as their default gateway, they should have access to the net now.

IPv4-forwarding could be enabled by editing /etc/sysctl.conf too, and is, after testing, a better idea for a permanent setting.

From the comments in my /etc/sysctl.conf file, I guess you may control all the stuff from there, but don't ask me how. :)