Amusingly, Oracle's patents don't cover a non-JIT compiler. Google could step around most of their troubles by including a Dalvik byte-code to machine-code compiler (based, perhaps, on Gcj) that runs when the bytecode objects are installed, rather then when they are executed. Android phones might need some more memory, then, but memory is still getting cheaper fast. It would be the more amusing if this resulted in better performance all around.
If Google were to abandon the JVM/Dalvik model and switch to a more optimizable intermediate representation, such as LLVM's, performance would be better still. That would, in turn, open up Android development to a much wider range of languages, and could make porting iPhone programs to Android much easier.