This isn't too hard to implement. I can see the box and controller getting out of sync, but if the controller hits the zone twice and it doesn't matter what order the two sub-zones come on in, then that seems fine.
You are right in that you need some kind of memory. Since the unit will have no power to it between uses, that memory needs to be non-volatile. A microcontroller with built in EEPROM would do fine. EEPROMs are only good for a finite number of writes, but that's 100s of 1000s at least so no issue there.
When the power to the switch box turns on, all it really does is run the micro. The micro then turns on one of N relays to route the power to one of the sub-zones. It also writes the new state to its EEPROM so that it will power the next sub-zone in sequence next time.
A tiny micro running at slow clock speed can easily handle this. The 5V current will be small so a linear regulator will do well enough and be simple. Get relays that can run directly from the full wave rectified AC so there are no power conversion issues. 24V AC after full wave bridge with filter cap should be around 30-32 Volts. "24V" DC relays would work but get a little warm. Genuine 30V relays may be harder to find, so you could get 24V relays and put a resistor in series with the coil. A reverse catch diode accross the coil and a NPN transistor with base resistor to the micro is all you need per sub-zone output.
Another thing to consider is that the micro needs to see one power up each time the main controller turns on the zone. This should be as simple as putting a little low pass filtering on the micro's reset input so that it doesn't start running until a 100 ms or so after power is applied. By that time glitches and switching transients should be over.
The main controller also needs to leave some off time between powering this zone so that it toggles to the next sub-zone. It will take some time for the voltage to drop before the micro loses power or is shut down by the reset circuit. It could be a second or two depending on what values are chosen.
The more I think about it, the more I'm realizing the trickiest part of this is the reset circuit. You want to make sure the micro runs cleanly once per power up, and that it goes into reset cleanly once on power down and not too long after power down. This is all quite doable, but something that needs to be considered.
There is no such thing as a "24 V LED". However, you can use a resistor in series with a LED so that the combination can be safely lit from 24 V. Let's say you want 5 mA thru the LED, and that the LED drops 2.1 V (typical of normal green LEDs). From Ohm's law, (24V - 2.1V) / 5 mA = 4.4 kΩ, which is roughly a suitable resistance.
Keep the power dissipation in mind. The resistor will drop about 22 V, which times 5 mA is 110 mW. That's getting close to the limit of a "1/8 W" resistor, so either make sure a 1/8 W resistor is properly mounted at the right temperature or use a 1/2 W resistor. Note that the power dissipation in the resitor is proportional to the LED current, which is one consideration for keeping the current low.
Best Answer
The simplest solution might be to find a 2nd relay that can handle the solenoid voltage and current and, activate it with a 12 (or 24) volt supply using the current 30 volt contact. Don't forget to put a flyback diode across the relay coil and the solenoid though.
Alternatively, you could choose an N-channel MOSFET rated for about 60 volts or higher and capable of handling 3 amps or more. You'll still need a flyback diode across the solenoid and, you'll still need an auxiliary supply to drive the gate but this time it should be limited to 12 volts in case you damage the MOSFET gate-source region: -