First of all, it's worth noting that Sun's JVM was written in C. C is a very popular language when portability is needed.
The C language is portable even though many C programs aren't. This is because C doesn't place as many restrictions on the programmer or make as many assumptions. If a C programmer wants his programs to be portable, he must put those restrictions upon himself.
In practice, that really isn't much more difficult than living with the restrictions Java forces on you. It's mostly a matter of being mindful of your endianness and primitive sizes, and using portable libraries like GTK+ instead of platform-specific libraries.
You could make a GTK+ target and C compiler that supported a virtual machine, even probably the JVM, and get existing code to work with very few changes. In fact, without the garbage collection, a C virtual machine would probably be much simpler. Why would you want to, though?
The reverse, compiling Java to native code, is likewise doable. That's basically what the JIT does. Why would you want to, though? I'm sure there are pet projects to do it "just because," but they are not in serious use.