No need to provide Internet, as most phones broadcast their WiFi MAC addresses to the world, even with the WiFi UI shown as "off".
In our lab environment we observed that in addition to periodic global MAC addressed probe requests, we were able to force the transmission of additional such probes for all Android devices. First, anytime the user simply turned on the screen, a set of global probe requests were transmitted. An active user, in effect, renders randomization moot, eliminating the privacy countermeasure all together.
https://arstechnica.com/information-technology/2017/03/shiel...
Amusingly enough, that's probably more because of an oversight by the manufacturer (who is probably just copying a reference design) --- they don't bother writing a "fixed MAC" and just leave the NVRAM blank, meaning the device doesn't actually have a MAC and generates a random one every time you turn WiFi on and off.
That's how it works on the Mediatek platforms that I'm more familiar with, and you'll find this is the case for a lot of the cheap Chinese unbranded phones. It's irritating when you need to connect to networks using MAC filtering, but I'm almost tempted to respond to all the "my MAC keeps changing" threads on XDA with "that's a feature, not a bug." ;-)
By "off", do you mean when the iPhone WiFi setting is set to off (not green)? How does that work?
Not green AND CROSSED OUT means the radio is actually turned off, and is supposedly neither listening nor broadcasting, if state of the settings applet is somehow more trustworthy than the state of the control center’s slide-out drawer widget.
Note that other non-apple handsets might just be doing whatever, unpredictably.