what do you mean "complex" and what do you mean "between"? do you want multiple machines doing nat? it's possible but i'd say dumb...
nat is probably what you want. look for a tutorial on google, it's the best way to go. a hardware router will indeed do nat, but it doesn't have the logging or blocking options having a full-fledged computer sitting between you and the internet allows. for one, there's no caching (although getting that going in linux is admittedly tricky).
You know, the more I think about this sorta thing the more I'm convinced it'd be easier to create a VPN of sorts. I was dicking around at Best Buy today and noticed that Linksys makes a VPN/Firewall Router/WAP device. It even has support for up to 50 connections. Just plop that baby in with a VPN client on the remote end and you'd be good to go. Any thoughts?