Yep, possible.
Questions which impact on design
are the new values from the database?
is the page allowed to be submitted and redrawn?
* is javascript allowed to be used?
If the page can't be submitted (and there are good reasons why that might be) then you need to use javascript to change the values of the combo box.
Now, if the values have to be obtained from the database then
each new combination set could be added to the html when it's first created with PHP produced javascript arrays holding those combinations. Then when a choice is made the right array is found and the combo is redrawn
you could have hidden iframes with tiny forms on them which are given the selected value and submitted. When they return they hold javascript which prompts the main form to redraw the combos.
I have a demo of iframes updating main forms which you can see at http://property.digitalrice.com/muck/example.php