On reset, all pins go to inputs, so if you have them 'pulled' to a default state (or at least a 'fail-safe/operational' state) with a pullup/pulldown, you should be ok. Then you can read the last state stored in eeprom, set the logic level on the pins, and change the pins to outputs as required. I would think it should be relatively easy to patch in a few pullup/pulldown resistors to a pin or two here and there.

Past that, sounds like some battery backup would be needed, or maybe some external latching relays.