How should I search up parts for basic hard-wired computer? (really basic, no, more basic than that)
You're going to need a lot of space.

http://www.homebrewcpu.com/ is an example of someone who's done this with wirewrap and TTL logic, not individual transistors. If you're serious about doing this, and don't want to solder, wirewrap is a good option. Another example: http://www.nzeldes.com/HOC/Handwired.htm . Wirewrap is easier to undo than solder, has less risk of damage to parts. It takes up more space and isn't good with high speed signals, which is why it's fallen out of use.

As for components, you'll need transistors. The NMOS 6502 CPU has about 3,500 of them. If you buy through-hole 2n3904 on digikey that will cost you about £60 and a lifetime of assembling them.

The relay option could lead you to duplicate the Zuse Z4: http://en.wikipedia.org/wiki/Z4_(computer) (attractive wooden cabinetry and 4kw power supply not included).

Clocking is the least of your worries; you could start with a pushbutton actuated by a cam on a cranking handle, giving you a variable rate of a few Hz.