Your question could be split into several parts; if you use Google through a browser, and that browser is not controlled by Google (say for instance, you're using a private window in Firefox on a laptop), then a VPN should protect you; google will only have access to the information Firefox provides it.
If you're using an Android phone though, and are logged in with your google account, then obviously Google has access both directly to your phone, and whatever info your browser is providing google.
So what then if you use a secure browser to access the Google web page form an Android phone? Depending on what you need, a VPN might keep you safe enough here: Google may be able to see your physical location using GPS, nearby networks, etc, but may yet not be able to connect that info with any action you do in the context of your browser.
In other words, Google may know where you are, but have no idea that it is you who are doing whatever you are doing on www.google.com in your browser.
Based on you question (specifically mentioning GPS, etc), I'm guessing this distinction is not of any great significant to you, but thought it might be worth mentioning anyway.
Beyond that, I can basically see two options:
- Use the settings under your Google Account to delete your location data, and choose to trust that Google really will delete your private data here. I would assume there are other settings too, to minimize the amount of data Google gathers about you, but again - it comes down to trusting Google in the end.
- Get a different / extra (non-Android) phone, on which you can limit Google`s access to your data.
Neither option is ideal if you're even slightly paranoid, but if you want your phone to be able to connect to a network (cellular or wifi), then I really can't see any other option.