I don't think it's gonna be possible without javascript. The onchange event of a select element *is* javascript as you know.
In my experience it's most efficient to use jQuery, bind an ajax call to the change event, and update/display the second box in the callback. That's the "web2.0" way. Upside - no page refreshes. Downside - pretty robust client side code.
If you're feeling more oldschool (php/asp'ish), you could with minimal javascript have the onchange event simply post the entire form, and on the server look at the posted fields and determine what to deliver back. Upside - minimal client javascript. Downside - full page roundtrips on field changes are a suboptimal user experience, they tend to annoy users and mess with the browser history.
A third option (I almost didn't even mention because it's exactly the opposite of your original question) is to populate the initial page with all the data you need for every combination, then do your user experience completely in javascript. If it's not a ton of data this is easy and efficient, and pretty dang safe now that all modern browsers are basically "pitfall free".
It really depends on which method will best fit the rest of your application.
If you avoid javascript because it's annoying, I totally agree - it is. But jQuery changed my life, and if you're not familiar with it the payoff is well worth the learning curve.
S