You can install Mullvad VPN (5€ per month, doesn't renew automatically, so you don't have to worry about follow up costs or canceling a subscription) without Google Play Services installed. You can get the app directly from their website.
But, and this is a problem of all VPN, they are mostly known to Google and Google doesn't like to open accounts made from IP ranges known to be part of vpn providers.
You probably will have more luck when you use a public wifi from a supermarket or buy a prepaid mobile network card with some data plan on it. Though the last will probably need to identify yourself to the provider, it will let you open an account without bigger problems and you can even present a real number to verify the account.
Last but not least, your IP isn't that much important when it comes to identify you. An IP just tells who owns an account, not who uses it.
It's like a licence plate. If someone else was driving or not will be investigated. Same for IPs, it's just a first hint, but neither prove nor evidence.
What is observed is behavior. Search patterns, what websites get visited and when and how long, interests, things you post etc.