Well, you could always ship software in platform neutral code and make the final transition to native code when they are installed (either with something like gcj or use some intermediate representation like LLVM does).
Really, the existing non-jit'ed Dalvik VM runs fast enough. If you think about it, their decision to ship a non-JIT VM and enhance the platform with JIT later is very much like Apple's approach with the iPhone of initially shipping the product without cut-and-paste and without any native API for third party apps, but then enhancing the platform later by adding those (and many other) features later. Both companies shipped when they had a platform that was "good enough", then have kept iterating and improving.
But anyway, what nimrody suggested is what they are doing - using platform neutral Dalvik bytecode and then transition to native through JIT.