Could this be worked around by installing a single shell app which then loads other apps internally? I think it's possible to dynamically load Dalvik byte code in ART these days, right?

Obviously permissions would be a problem, as you can't update the app manifest, so there would either have to be one shell app per publisher (which would at least solve the problem of installing updates for their apps) or the shell would need its own internal system for managing permissions (like a browser does). Maybe it could also sandbox different apps from each other in different subprocesses, unless that needs root privileges, but maybe it's possible with Landlock?

Or we can always fall back to the "sweet solution" Steve Jobs offered us with the original iPhone, and just let the web browser be the shell.

Or implement everything as WeChat mini programs.