More googling, Shizuku² does this already in a polished way and exposes an API for other apps. Some related-ish apps are SAI³ (for installing split apks) and Canta⁴ (removing system apps).
EDIT: Even more googling, the whole setup already exists in Obtainium (i.e. F-Droid but with Github Releases) apparently so apps show up as being installed via Play Store and subsequently be usable in Android Auto⁵.
So hypothetically you can install stuff day one on a stock phone after this atrocity is turned on.
[2]: https://shizuku.rikka.app/
[3]: https://f-droid.org/en/packages/com.aefyr.sai.fdroid/
[4]: https://f-droid.org/en/packages/io.github.samolego.canta/