You are right, in presence of NAT, there is no way (no easy, built-in way) to distinguish two machines behind NAT from two connections coming from one computer. NAT translates two different local IP addresses to the same externally visible address (only with different ports, just like two connections on the same machine would work, too).
The easiest and most obvious solution is to let users log in with username and password. Simply do not let any username log in more often than once simultaneously.
Another approach is that you send some "unique" identifier with every connection request, such as the MAC address or another of the computer's "serial numbers" that is reasonably unique (harddisk serial number, GPU model, local IP address). Store that identifier while a client is connected (not any longer, this is neither needed nor desirable), and do not allow another connection with the same identifier (or, the same identifier and the same publicly visible IP address to be sure -- otherwise two people might accidentially have the same cheap no-name ethernet card with a duplicate MAC and you block them. Yes, such cheap ethernet cards do exist.).
Obviously, this only works if you use your own client program and use a protocol that supports something like a "cookie" And, again obviously, since the client program is physically present at the user's computer, this can be forged by a moderately skilled user. Your users might also be grossly unhappy if it is revealed that you "spy on personal data". Which isn't really what you're doing, but in a very contrieved sense, one could see it that way, and certainly some very vocal people will publicly accuse you of doing exactly that, if they realize you're doing it.