Sandboxed Google Play receives no special access at all, so you can deny it all permissions if you want, but you should grant network (and maybe notifications) permission for it to actually function.
So an application of course can use other android services if it declared that, that's why it can see whether it's running or not. But you are in full control whether google play services is installed, and what it can use.
Of course this may break certain apps (Google maps location sharing will probably not work with the location permission denied for play services), which may or may not degrade gracefully.