Hawke,

Take a look at the netfilter stuff:

    http://netfilter.kernelnotes.org/

I haven't looked at very much yet and would be interested in hearing
about it.

I did get NAT working a few years ago (though it wasn't easy) using
Alexey Kuznetsov's route2 code from ftp://ftp.inr.ac.ru/ip-routing/. 
I have no idea if this stuff still works or not.

I think you're better off starting off with the netfilter stuff and
see where that leads you.

Kevin