Using one router for multiple networks is not complicated in the slightest. However, I'm a bit comfused with regards to the Internet connection, as you first say you want to use two Internet connections, but in the example only one NIC has a public IP address. Could you clarify?
Otherwise, your setup will work if you simply:
- assign IP addresses to each interface
- enable routing on the Linux box
- configure clients on both network to use the relevant IP address on the Linux box as a gateway
- and finally NAT overload all outgoing traffic behind a public IP address