It takes a couple more steps but some games use a multi app install process.
You break up the game into multiple apk's which gets around the Android limit.
So you have the primary apk that launches the game but then secondary apks that are essentially patches.
No clue how complicated this is from a dev perspective but it's one of the simpler options I have seen on the user end.