Running java without installing jre?

For creating native executables, you can use Excelsion Jet, which compiles Java to native code. We used it for a project at work, and we had to perform zero modification to the original source code (which targetted Sun's JDK).

You can use Launch4j for this. Well documented and easy to use. While the resulting program still needs a JRE to run, you don't have to install the JRE on the target system. You can just copy it with your application and tell Launch4j were to find it or just wrap it up with everything else.