What do you mean it would "show up in everyones downloads"? Google Play Services are constantly being updated on peoples phones. Literally nothing besides Google's decision not to prevents these updates from containing a backdoor.
If it's bound by the OS permission system and doesn't have full root, it might be able to replace apps with another version that is signed by a different key (using the "programmatic app installing" permission). However, that would wipe the app data and break app updates. Not even adb can replace an app with one that is signed by a different key without data loss (adb install -r). And I'm sure a lot of developers ask for this feature.
(I haven't actually tried whether you can really successfully switch signatures on an APK that way without losing all user data, tough)
Additionally, starting from Android 10 it seems that there is a new official feature allowing data to be kept after uninstallation if an app opts-in (https://stackoverflow.com/questions/58750567/how-to-enable-o...).