Storing an LED's previous state even when power is removed

You need one of these:

_{(source: vandykes.com)}

A bit retro, but meets your requirements exactly!

The point is, there are only a few ways to remember the state of an electric circuit with no power applied, and mechanically is one of the most common. The other ways can't be done with the types of components you've listed.

A bi-stable switch as Dave Tweed mentioned will certainly work. Another way is to use a tiny microcontroller that has EEPPROM built in. There are some PIC 12 available with EEPROM. The micro reads the two switches, drives the LED, and stores the last state in EEPROM, which it then recovers on powerup.

If the flip-flop uses only a tiny bit of current, such as if it's CMOS, you could supply power for a day or more to the flip-flop with a battery. Keep the battery trickle-charged with the external power. A super-capacitor might work as well as a battery. Use only external power (not the battery/supercap) for the LED and its driver, and any other circuitry. A diode can keep the the memory-keeping low-current circuitry separated from the power-hungry LED.

BTW "NAND" in regards to flash memory isn't really the same as the basic logic gate. Flash memory involves shoving charges across an insulator to an island of semiconductor or metal, and nand gates are involved in some manner to read/write the data, but I'm no expert on that. Plain old NAND gates in TTL, NMOS or CMOS chips can't hold data at all.