Google knows the GPS location of almost every Wifi router, even if nobody has ever (successfully) connected to it with location services. By design, Android will search all Wifi SSID's and send the GPS coordinates back to Google, so that if another phone not using location services connects to that router, Google knows their location by cross-referencing with the stored GPS coordinates.

Unfortunately, we can't even entirely trust our phones then either. You can turn on airplane mode in the OS, but it could still choose to reactivate the radio for short bursts without you knowing. Or the the radio could be set to phone home on a regular basis on its own recognizance. This could potentially occur even if the phone is turned off.

There is no way to ever completely trust a cellular device.

This would be easy to check by checking radio signals emitted for the phone. This might be an expensive experiment to set up, but easy to check.