Tested on Proxmox 4.2

Basically you should have already a vmbr0 in your /etc/network/interfaces, which looks like that

  auto vmbr0
  iface vmbr0 inet static
    address 1.1.1.1
    netmask 255.255.255.0
    network 1.1.1.0
    broadcast 1.1.1.255
    gateway 1.1.1.254 (or something else as 254)
    bridge_ports eth0
    bridge_stp off
    bridge_fd 0   
You just need to add another bridge for your NAT Boxes:
 

  auto vmbr2
  iface vmbr2 inet static
    address 10.21.21.254
    netmask 255.255.255.0
    bridge_ports none
    bridge_stp off
    bridge_fd 0
    post-up echo 1 > /proc/sys/net/ipv4/ip_forward
    post-up iptables -t nat -A POSTROUTING -s '10.21.21.0/24' -o vmbr0 -j MASQUERADE 
    post-down iptables -t nat -D POSTROUTING -s '10.21.21.0/24' -o vmbr0 -j MASQUERADE
Restart your Network:
  service networking restart

You also need to assign your VM's to vmbr2, example Network config for your VM's:

Gateway: 10.21.21.254
Netmask: 255.255.255.0
IP: 10.21.21.4

  allow-hotplug eth0
  iface eth0 inet static
        address 10.21.21.4
        netmask 255.255.255.0
        network 10.21.21.0
        broadcast 10.21.21.255
        gateway 10.21.21.254

You can Forward one Port like this:

  /sbin/iptables -t nat -A PREROUTING -i vmbr0 -p tcp --dport 1500 -j DNAT --to 10.21.21.4:22

or a Port range like that:

  /sbin/iptables -t nat -A PREROUTING -i vmbr0 -p tcp --dport 1500:1600 -j DNAT --to 10.21.21.4

You can setup your own bash script with these commands and add it to the Startup: [[startup|Run a Script while Booting]]

Or just put it into your Interfaces like that:

  auto vmbr2
  iface vmbr2 inet static
    address 10.21.21.254
    netmask 255.255.255.0
    bridge_ports none
    bridge_stp off
    bridge_fd 0
    post-up echo 1 > /proc/sys/net/ipv4/ip_forward
    post-up iptables -t nat -A POSTROUTING -s '10.21.21.0/24' -o vmbr0 -j MASQUERADE 
    post-down iptables -t nat -D POSTROUTING -s '10.21.21.0/24' -o vmbr0 -j MASQUERADE
    post-up iptables -t nat -A PREROUTING -i vmbr0 -p tcp --dport 2222 -j DNAT --to 10.21.21.4:22
    post-down iptables -t nat -D PREROUTING -i vmbr0 -p tcp --dport 2222 -j DNAT --to 10.21.21.4:22