In VirtualBox, how do I set up host-only virtual machines that can access the Internet?

I can get the setup I want by setting up two adapters on the vm.

VirtualBox 4.2.12
Ubuntu 12.04 guest

In VirtualBox > Preferences > Network, set up a host-only network.

Mine is called vboxnet0, it is manually configured:
ip 192.168.56.1
netmask 255.255.255.0
no dhcp

Then, in the network settings for the virtual machine, set up two adapters:

Adapter 1
host only, vboxnet0

Adapter2
NAT

Boot the virtual machine and log in through the console VirtualBox provides.

Run this to see your adapters:

ls /sys/class/net

In my case the adapters were named eth1 and eth2 (and lo, the loopback interface).

Then, edit your network configuration.

sudoedit /etc/network/interfaces


# The loopback network interface
auto lo
iface lo inet loopback

# Host-only interface
auto eth1
iface eth1 inet static
        address         192.168.56.20
        netmask         255.255.255.0
        network         192.168.56.0
        broadcast       192.168.56.255

# NAT interface
auto eth2
iface eth2 inet dhcp

Note that eth1 has no default gateway specified. eth2 will get a default gateway from dhcp.

Update March 2018

See this answer from @Hugo14453 for an updated version that works with Ubuntu 17.10 and newer.

I could solve my problem with a mix of Christian Long solution. I added 2 adapters:

Adapter 1 - NAT

Adapter 2 - host only, vboxnet0

The only diference was in VM's interfaces file:

sudoedit /etc/network/interfaces

# The loopback network interface
auto lo
iface lo inet loopback
# NAT
auto eth0
iface eth0 inet dhcp
# Host only
auto eth1
iface eth1 inet dhcp

In VirtualBox Network config I left DHCP checked.

After a VM reboot everything worked fine.