Unfortunately, I don't see any way you can do this without a page submit.
Detecting whether JS is available through the HTTP_USER_AGENT is all well and good, but this is easily modified and you can't guarantee any information is going to be there or be correct.
BUT - since JS requires not only JS to be available - but also enabled there is no way you can find this out without trying to run some JS in the first place and returning the result to your script.
The question is, why can't you do a page load??? If you wanted to be a bit more sly, you could create an invisible frame and do the detection in there, resubmitting to your server without the user knowing anything (unless of course they check out the source code etc)