NAT doesn't really have much to do with it, other than you with NAT, you certainly have a device on your network that's capable of being a transparent proxy, whereas without NAT, you could just have a unmanaged switch to share your upstream connection between multiple computers; assuming your provider is enlightened and provides ethernet or an ethernet bridge with nothing else in the way.