Para actualizar los Google Play Services no necesitas ser root ni hacer nada especial. Simplemente pasa por aquí...
http://www.apkmirror.com/apk/google-...play-services
...y descarga la versión que corresponde a tu sistema (para el S4 con KitKat es la que termina en 038). La instalas y listo.