I did the same (4-bit cpu, 11 instructions) in my Microprocessors class, out of 74-series logic, one GAL20V8 to handle the SLE instruction and an EPROM (not an EEPROM - one with the clear window you exposed to UV light to erase.

That was also where I learned about ground-bounce & dynamic IR-drop effects due to those long looping wires between breadboards.

That was a fun class.