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: 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