You can download an apk and launch the package installer activity to install it. In latest versions of Android, you'll need to serve the apk through a ContentProvider. I tested this myself, it works, even if the app is updating itself.

But I think you can actually still load arbitrary dex files using a ClassLoader? I thought that the update was only affecting JNI libraries. I remember reading how they wanted for any and all executable code to come from a signed package. Even then, if you're determined enough, you can load arbitrary native code by allocating some rwx memory pages and copying it in there ;)