You do not need JDK (Java Development Kit) on the machines where you want to run your java byte code. You just need JRE (Java Runtime Environment). JRE can be downloaded from http://java.com/en/download/manual.jsp (Approximately 15 MB).
You can just download JRE and distribute it with your game. As it is much smaller in size as compared to JDK
There is no way you can run byte code with Java Runtime environment. There are some projects that allow you to make exe (Windows/DOS Executable) file of .class file.