Two interfaces, two addresses, two gateways?

You are misunderstanding the problem. Not every packet is a response and not every packet can be matched to some other packet such that "same network interface as they came in on" makes sense. What you want to do is select the gateway for a packet based on its source IP address.

This is called source-based routing or policy routing. You can do it with a simple iptables rule, but the best way is to set up two routing tables, one for each public source address:

First, create two tables (Replace <NAME1> and <NAME2> with sensible names for your two providers, same with IP1, DEV1, and so on):

echo 200 <NAME1> >> /etc/iproute2/rt_tables
echo 201 <NAME2> >> /etc/iproute2/rt_tables

Add a gateway to each routing table (if needed):

ip route add <NET1> dev <DEV1> src <SRC1> table <NAME1>
ip route add <NET2> dev <DEV2> src <SRC2> table <NAME2>

Then a default route:

ip route add default via <IP1> table <NAME1>
ip route add default via <IP2> table <NAME2>

Then the rules to select the route table based on the source address:

ip rule add from <IP1> table <NAME1>
ip rule add from <IP2> table <NAME2>

See Routing for multiple uplinks/providers for more details.

David Schwartz's answer is excellent, but you can simplify the routing rules a bit by having just one extra table, and using your default route for the other. I have a server that's behind two NAT gateways, and I recently went through the process of recreating that scenario between a bunch of VMs. My /etc/network/interfaces looks like this:

auto lo
iface lo inet loopback

auto eth0
iface eth0 inet static
    address 192.168.13.13
    netmask 255.255.255.0
    up ip route add table optus default via 192.168.13.10
    up ip rule add from 192.168.13.213 table optus
    up ip route add default via 192.168.13.11

auto eth0:0
iface eth0:0 inet static
    address 192.168.13.213
    netmask 255.255.255.0

(this is for a setup where the two ISPs are Optus and iiNet, hence the table name of 'optus')

This, plus the line in /etc/iproute2/rt_tables creating the table, should be all you need. You'll have two IP addresses; traffic from 192.168.13.13 will go out via 192.168.13.11, and traffic from 192.168.13.213 will go out via 192.168.13.10. Configure those two gateways to do their port forwarding appropriately (192.168.13.11 forwards stuff to 192.168.13.13, and 192.168.13.10 forwards stuff to 192.168.13.213), and the rest should take care of itself.

You may need to tweak things a bit for your situation, as you're using public IPs directly, but something like this should still work. Also, it's a lot easier to do these things in /etc/network/interfaces and then git-manage that file, rather than try to remember how you had it set up, two years later when the system has to be rebooted!