Ideally native app wouldn't require installation any more than a web app would. There is no reason why native apps couldn't be loaded dynamically on-demand from the internet. Java Web Start did something like that, but like all Java it was bit clunky.
Of course current operating systems have poor support for such kind of behavior, but that could be remedied. I think the "activities" concept in Android already is first steps towards that goal.
There are inherent problems which are not Java specific. Your app would need to have very few rights for starters, the sandbox should be as small as possible (like browser/JS).
If you have different permissions and a complex sandbox with a runtime that supports classloaders, you run into the same security problems that Java currently enjoys for applets.
Security, permission management, and sandboxing would be critical concepts of a system running code from potentially untrusted sources. But I don't think the security problems often associated with Java and Flash are inherent for such sandboxes. Web browsers themselves are an excellent example of sandboxing that seems to have stood fairly well against attacks. And NaCl demonstrates that the security model of web browsers is extensible to native code.
Of course current operating systems have poor support for such kind of behavior, but that could be remedied. I think the "activities" concept in Android already is first steps towards that goal.