There's some real confusion about Android here. Android already has its own bytecode format (Dalvik), and it's unlikely that NaCL would replace it, if only because NaCL is tightly tied to the underlying processor instruction set, while Android has already shipped on at least two (ARM, MIPS), and been ported to at least one more (x86).
It's also already the case that a third-party app which requests appropriate permissions can replace the standard contacts app --- in fact, there are several alternate contact managers already in the Android Market. Of course, the user must confirm that they want to allow the app to manipulate contacts, and apps that don't request that permission can't ordinarily do that. (Malicious apps can manipulate contacts without asking permission on the customized versions of Android shipped with several recent handsets, per news from the last few days, because the vendors doing the customization screwed up, but that's another rant altogether...)
I think you're focusing too much on the underlying technology, Dalvik is ultimately little more than a layer of indirection, that could easily disappear deeply beneath the covers of a 22nd century OS, hidden by a simple click of a 'Build' button in an IDE, much like Win32 did.
Similarly, Contacts was only used as an example, as it is prominent and simple to understand. The main reference made there was to the data the Contacts UI represents, which ultimately backs on to some class library that ultimately is controlled by the platform (as I understand it).
> "...that could easily disappear deeply beneath the covers of a 22nd century OS..."
So we have a bit of time to form a reaction strategy then. ;-)
Are we even sure Android will run on the quantum-singularity computronium that we will have by then, or that the Google meme-avatar will still be on, or near, Earth?
Maybe they want to start Android from scratch? It might be worth it if this means Google will handle all updates from now on. But it better mean that, because otherwise I don't like the idea of making it impossible to create custom ROM's, while still not getting updates like it happens now.
It's also already the case that a third-party app which requests appropriate permissions can replace the standard contacts app --- in fact, there are several alternate contact managers already in the Android Market. Of course, the user must confirm that they want to allow the app to manipulate contacts, and apps that don't request that permission can't ordinarily do that. (Malicious apps can manipulate contacts without asking permission on the customized versions of Android shipped with several recent handsets, per news from the last few days, because the vendors doing the customization screwed up, but that's another rant altogether...)