Primeiro de tudo: você tem certeza de que não está faltando apenas o módulo carregado?
Tente:
modprobe iptable_nat
Caso contrário: sim, você também poderia fazê-lo sem NAT configurando para o endereço de rede determinado uma rota estática para a interface desejada, mas isso implica que também do outro lado você tem que fazer o mesmo (na verdade oposto: publicar uma rota para sua rede) roteamento também. E, claro, neste caso, todos os hosts em ambas as redes podem ser teoricamente visíveis (o que pode ou não ser uma coisa positiva dependendo de suas necessidades)