NAT and DHCP are totally independent technologies, which do not rely on each other at all.
The first concept to understand is one of network segments - simplifying slightly, all IP addresses in the same IP range are in the same segment. A DHCP server listens on a given segment for requests for an IP address and offers it when asked. A DHCP server needs to listen on the same interface as the segment is on - thus it can run on a computer with a single network card, or on a router (in a home network it would typically run on the router, serving addresses on the LAN network).
On a typical home router NAT is run on the WAN interface, and relables packets leaving the network with the external IP address. It holds a translation table so it knows which internal machine requested what. In this way its possible for a single real-world IP address to be shared between multiple workstations.
Your question "when I connect two different computers they both get different external IP's. How can this happen? Shouldn't my router be NAT since it protects my local IP Address?" presents something of a curveball. The answer is yes, in a home network, any devices behind NAT would typically share a single external IP address.
There are a few possibilities why you are getting different IP addresses, including -
Your provider is using Carrier Grade NAT, and and is, in effect doing double-nat. Carrier Grade NAT requires the use of more then 1 IP address, so it could be that different TCP sessions are being allocated different IP's
You may not be using NAT at all, and your provider is providing you with a subnet of IP addresses which are real-world routable. This would seem somewhat unlikely in a home environment (and indeed there are security implications to it), but not uncommon if requested on business accounts.
Its conceivable your router has more then 1 real-world IP address on it and is doing more complex NATTING (similar to carrier grade nat) to overcome some limitations of NAT.