Thank you all! With a combination of those two hints, I was able to uninstall the Google Play Services updates pretty easily without activating USB debugging, installing SDK, and all that.
Seems to be working for the time being. Automatic updates are disabled. I hope that prevents it from happening again.