Doing it with a microcontroller "feels" wrong: you might as well program the microcontroller! If you're building your own computer for learning purposes, there are two basic approaches:
1) Discrete 74 series logic. You can get an ALU: http://www.taydaelectronics.com/74ls181-74181-arithmetic-logic-unit-function-generator-ic.html and some flip-flops. This approach is hands-on and can be debugged (slowly) with a logic probe or basic multimeter. It will also involve a lot of wiring. The parts are effectively obsolete but still seem to be available.
Discrete RAM: digikey parameterised search suggests this 32Kbyte SRAM, good for speed of a few MHz. (Note: do not attempt high speed digital logic on breadboards; anything above 1MHz is likely to have trouble).
Registers/Program counter: flip-flops
Programming (in order of authenticity/effort): Toggle it in manually with a set of switches; or build a small ROM from diodes; or build a paper or magnetic tape loader; or program an EPROM; or get an Arduino to pre-fill the SRAM.
2) Use an FPGA, and write it in Verilog or VHDL. This focuses effort on the "design" side rather than the "construction" side, and can be more easily simulated on a PC to validate your design. It's much, much more flexible. The only downside is that the result is still a black blob, albeit one where you understand the internals.
For this case you could more easily program it by embedding a ROM image, and use the FPGA's internal block RAM.