2 momentary switches, controlling 4 outputs in sequence using latching type relays
I'd consider using a binary up-down counter like this. Decode the two least significant outputs with a 2-4 line decoder and then use 4x MOSFETs for driving the solenoids. Forget about latching relays - this is a more reliable solution I would say.