I know my friend's external IP (from whatsmyip) and internal IP (e.g 192.168.1.x) and he knows mine. How do I establish a TCP connection with him?
Is it possible to do it without any port forwarding? Or do I require a server with an external IP to transfer messages between me and him?
You cannot do that because of NAT(Network Address Translation). The public ip you see by whatsmyip.com is the public ip of your router. Since different machines can connect to the same router all of them will have the same public ip( that of the router). However each of them have an individual private ip assigned by the router. Each outgoing connection from the private network has to be distinguished hence the router converts the connection(private ip, port) to a (different port) and adds it to the NAT table. 
So if you really want to have a working connection, you should have to determine both the internal and external port for both ends and do the port forwarding in the router. Its a bit tricky and hence techniques like TCP hole punching are used.
Connecting to a known external ip and internal ip without port forwarding