I've not seen too many games where you can't change the port it uses. I recall you can change the port of use on games as far back as Warcraft II.
Dig a little deeper into the game settings. A lot of games will use the same port so they generally will allow you to change it. When you host a game and are setting it up, you can normally change the port right there.
The other option would be to put one computer into the DMZ. You would lose the 'firewall' of the NAT router but otherwise would be good the game.