As Houston Fortney says in a comment, you need a physical phenomenon which exhibits memory. Furthermore it must be electrically controllable, ideally reversible or somehow resettable, and electrically detectable. And presumably it has to be accessible for home construction.
A latching relay has been mentioned - for a small number of bits, a small number of relays is viable.
Other options :
Magnetisable ferrite cores. You can occasionally buy surplus "planes" of core memory left over from 1960's computers. The electronics to support these is feasible in discrete transistors (probably needs inappropriate voltages for common ICs) but definitely not an exercise for the faint-hearted.
An E-Ink display from something like an Amazon Kindle, and a camera, mounted in a frame.
A variation on this : a matrix of high-power SMD resistors on a PCB under thermal printer paper, and a camera. The electronics to power the resistors to make dark spots on the paper will be much easier than driving the E-Ink display if you insist on doing it yourself. To clear the memory, simply replace the paper.
A network of fuses or fragile components which you can destroy by overcurrent, or read by applying lower current. These used to be available as "fusible link PROMs" in the 74 series TTL logic family but in principle you could easily make your own with a matrix of short thin wires, and high current row and column drivers. Resetting a bit requires soldering though. Unless you make it from a matrix of 3V mini lamp bulbs, which you "read" at 3V and "program" at 6V, in which case all you need to do is replace all the bulbs in a row to reset that byte.
Model control servos or stepper motors driving potentiometers or rotary switches. If you can control position to about 1% accuracy you may get 6 or 7 bits from a potentiometer, or 4 bits (reliably!) from a hex coded switch.
By now I expect you're taking another look at that non-volatile memory...