that is really very weird.. any browser should not be affected if java or any other plugin/runtime isn't installed.. it could be that you didn't completely uninstall java meaning that there are still references of it in the registry that kmeleon detects and yet the registered files aren't there causing kmeleon to actup.
check in kmeleon help>about plugins and see if there are any entries for java jre.
if there is.. you'll need to dig into the registry and remove all java classes and enteries for all java plugins (npjavaxx.dll)
i'd also recommend installing an older version.
check this link:
http://www.oldapps.com/java.htm
try version 1.6, it's the one i use and so far it hasn't caused any issues nor did any site or java application have asked me to update.