The real truth: If Dalvik violates patents, just use a different programming language like, oh, I don't know, C, C++, D, or
Go for Android! It would make Android so much faster, considering all these are compiled languages, that Java-based Android would be unnecessary.
How about Python? Integrate a Python interpreter into the kernel and write Android applications that are literally interpreted by the kernel. This sounds like a pretty good replacement for Java-based Android, don't you think?