Sugestão (não testada)...
Instale o pacote "openvpn", em seguida crie uma interface virtual TAP.
sudo apt-get install openvpn
sudo openvpn --mktun --dev tap0
Configure essa nova interface da forma que quiser; eu sugiro usar o arquivo /etc/network/interfaces:
auto lo
iface lo inet loopback
auto tap0
iface tap0 inet static
address 192.168.100.1
netmask 255.255.255.0
broadcast 192.168.100.255
network 192.168.100.0
Use o comando abaixo pra ativar a nova interface virtual.
sudo ifup tap0
Os comandos abaixo confirmam que ela está funcionando...
ifconfig tap0
ping -c 4 192.168.100.1
Em seguida, configure o VirtualBox pra associar as interfaces bridge a essa nova interface virtual tap0, em vez da interface física eth0 ou da interface ppp0.
Se tudo der certo, dá até pra compartilhar a conexão da internet pra essa interface virtual.