Yes, you can build a computer from scratch. 4-bits is a good choice, since it uses considerably less hardware (but obviously more than half) of an 8-bit computer. The first commercially available microprocessor, the 4004, was a 4-bit device. Its successor was the 4040, also a 4-bit device.
In the home-brew computer field, 4 and 8-bits are the norm. 16-bit computers are less common, and I have never seen a 32-bit home-built computer. (Note -- I am limiting this discussion to designs where the entire computer is built from scratch, i.e. they don't use a conventional microprocessor chip; however some homebrew designs do use the 74181 4-bit ALU, commonly found in minicomputers such as the PDP-11).
Here are five 4-bit computers that others have built. In three of the examples, complete schematics are available.
Fourbit, 4-bit homebrew CPU design, and schematic available
4 bit computer built from discrete transistors design available
Build this 4 bit CPU from TTL ICs. design and schematic available
APOLLO181 Homemade 4-bit TTL Processor design and schematic available, uses 74181 ALU
Homebrew 4-bit Computer using TTL ICs Youtube video only
One of first things you will need to do is figure out the instruction set. This is the fun part, as far as I'm concerned, as you visualize how your computer will run your programs. With just a 4-bit memory path, you will certainly need some instructions longer than 4 bits. So do you make all instructions double-wide? Or use variable length instructions? You choice.
Check out the instruction sets for the computers listed above, in addition to the 4004 and 4040, for ideas.
There are a lot of examples in the Homebuilt CPUs WebRing, which include some more 4-bit as well as 8-bit and 16-bit home-built computers. There's even a couple of relay computers.