I guess I forgot to mention I don't have Google services installed either altough that isn't any different than having background location access disabled for the Google Maps app on an iPhone.

Is there some other mechanism that Google can gather location data?