Each packet routed outside you intercept twice – first on the internal interface before NAT is applied and second on external interface after NAT is applied and vice versa for packets coming on the external interface. In theory you can match these packets (by IP address information + IP ID + TCP/UDP headers information) and build your own copy of NAT table but collisions are still possible especially if the router is heavily loaded.
I would recommend implementing NAT in the same module which implements shaper, this would save you lots time. NAT is relatively easy to implement (if you are not targeted to support complex protocols like H.323), an example this simple application has taken one day to write http://www.ntkernel.com/w&p.php?id=31