Irrigation Valve (24VAC Solenoid) Multiplexing
If your MSP430 experience is C based, you should easily be able to switch to another series. I'm saying this because AVR controllers have EEPROM (the memory you need) on-chip. The EEPROM of the AVR-Tiny13 has 100 000 erase/write cycles, that should be enough for a 100 years. If you use MSP430 you'll have to add the EEPROM externally. This one even has 1 000 000 erase/write cycles.  

There's nothing to it, really. Upon power-on the controller checks which valve was last used, selects the next one, stores this and shuts down.  

You don't have to worry about the power the controller requires, that's peanuts. The relays will need more.
You have to rectify the 24V AC and use a voltage regulator to get the DC voltage the microcontroller requires. The LM2936 can handle the high input voltage, The 50mA are more than enough for what we need (Feeding a controller and driving a transistor.
The rectified AC voltage will also be used to power the relays. This voltage will be 32V, and there are 36V relays which will operate guaranteed at 32V, but they're rare. Use a power-economical relay like this one. There's a 24V which can handle voltages up to 50V.

I don't see a need for diodes, except as flyback on the relay coils.  

Olin rightly points out that the reset circuit needs special attention. If it resets more than once you would skip a sprinkler, so that's not disastrous, but it can be avoided. One way would be to use a low-pass RC filter with a rather long RC time, but microcontrollers often insist on a minimum dV/dT on their reset pin, so that may need something extra. This could be a reset controller like the MAX809. (Use this one from OnSemi, not Maxim's). This will give a nice reset pulse.