Yes. You should publish your new APK (e.g. v1.0.9) on Play Store immediately after you publish your new web services.
Before doing it, I hope you have done following things:
I assume here currently live version of APK is v1.0.7
Create another version of APK (e.g. v1.0.8) which will check if new web services are published or not. If the new web services are published then prompt user to download the updated version of this app. Tell user in a message about the reason for this update. Also, tell that app won't work if you don't update.
Upload this APK v1.0.8 on Play Store. Wait for few days to roll out this APK to maximum users. Till then you will have to work on development of new APK and new web services.
Once the new APK v1.0.9 and new web services are ready for production, publish both of them at the same time.
We have done this with one of our apps and it worked perfectly well.
This can be better solution for you. I hope it helps.