I Rooted My Phone and Uninstalled Google Play Service
I had same problem few months back. Then what I did was:

I used a second, identical device (running the same Android version), and from there transferred all the components I had accidentally uninstalled on the first one, using some sort of apk sender application.