I'm not an Android dev, but I would assume that Play Store has always had special permissions in order to be able to install applications, so Google need only deploy an updated version of Play Store for both old/new devices, and that updated version of Play Store have the necessary code to use its privileges to install Play Services and grant Play Services special privileges.
Play Services must be playing by the same rules as everyone else or it just wouldn't work on as many devices as it does.