When I replace the Client(IP, PORT) of the inner packet with the NAT External(ip, port), what port number should I used for the NAT external? The same with the Client Port or a new one? Is that must be a free number that no one uses it? How do I generate this port number.
When you substitute inner source IP with external one but don’t substitute inner port this is called static NAT. When you substitute inner source port in addition to IP this is called dynamic NAT. You can use any free port number (an example just take some rarely used port range like 10000-64000 and allocate ports from there).
PS: where can I get the code of Checksum Calculation?
That depends from the progarmming environment you use, an example some C and Delhi code is available on this board.