Thomas, you are spot-on with your realization. You must be connected to the same network in order to be able to scan network hosts with nmap.
Now, think about what networks you might be connected to that your target may also be connected to.
- External Untrusted (the Internet)
- DMZs (hosts that are connected to both trusted and untrusted networks)
- Internal Trusted (home/business network)
Now to your questions about how a pentester would scan hosts on these networks with nmap. Let's take them one at a time...
If we are putting this in the context of a penetration test scenario, a pentester could spin up an Internet facing host either with a cloud service like AWS/Azure/Docker/etc, install nmap, and scan the client's Internet facing hosts. This list of hosts can be given to the pentester by the client or can be built using DNS queries, ping sweeps, and/or searching for registered sub-domains. The pentester will most likely find hosts like web servers and mail servers as well as various other services. The pentester might also be fortunate enough to find an internet-facing device like a web camera or other IoT device. Maybe even a misconfigured host that shouldn't be facing the internet, but accidentally was patched down to the wrong port, put in the wrong VLAN, or a multitude of other security misconfigurations that could expose a host to the wild-west that is the Internet.
At the end of the day, any of these external facing hosts could be discovered, enumerated, and scanned using nmap.
Here we have hosts that are connected to the Internet as well as have some connection to the private internal trusted network. They are what's called multi-homed, which is a $20 way of saying it has multiple network cards and are connected to different networks simultaneously. A lot of times you see this as a web server running a web application that is connected to a database. Since it is Internet-facing, our External scanning rules apply. Then if the pentester is able to exploit a vulnerability in the web application, they now have a "pivot" into the internal trusted network. Then pentester could then install nmap on the compromised host or proxy nmap through it and use it to scan hosts in any other networks that it is connected to.
Here the client may grant a pentester access to the internal network purposefully for the sake of finding out how far a real threat could penetrate into the internal network if they were able to access it. This is called an Internal Pentest. But the pentester may gain access to the internal network by attacking the wireless network, finding an open ethernet port, hijacking the network connection of an IP phone, network printer, or some other network device. They could drop a LAN Turtle which will create a tunnel through the internal network and out to the internet, giving the pentester a backdoor. As you mentioned, the pentester could use malware via a phishing campaign. These are just a few common examples.
So, what is the goal of nmap? It is a tool to find open ports on a network host and enumerate the services running on those ports. It also does host discovery and some vulnerability scanning. The good news is that just because you're not jacked into a private network doesn't mean that there aren't internet-facing targets that could be the open window into that private network, but it all starts with nmap.
I hope that helps to clear things up for you.