Does the app work on phones without Google services?
Yes. On devices without Google services — for example, current Huawei phones — spoofing works normally, and so do the map and search: they are built on Yandex Maps, not Google Maps.
The only thing that uses Google services is checking the state of the system “Google Location Accuracy” setting. On a device without these services the request simply fails, and the app determines the same state another way. The difference only shows in hints: the app is slightly less often able to say exactly which system setting should be turned on.
Everything else — the map, address and place search, voice input, spoofing itself, website sync — does not depend on Google services at all.