Yes, it is possible - after all, the Arduino is essentially just a bunch of incredibly tiny transistors. Early computers, before ICs were invented, were built from transistors. Before that it was valves. Before that it was relays. All just, at the end of the day, switches.
Would it be a practical project? Not really, although someone has done it (not for the AVR CPU, but the concept is the same): http://www.megaprocessor.com/
How would you start? Well, first off you'd create the basic building blocks of a CPU, which is logic gates. There are two basic ones that can be combined together to make any other gate: the NAND gate and the NOR gate. You'd pick one of those and put lots of them together to make the basic sections of the CPU. Then those blocks connect together to form the CPU. More logic gates go together to make the IO functionality, memory, interfaces, etc.
Basically:
- Transistors combine to make NAND gates (or NOR gates if you prefer that form)
- NAND (or NOR) gates combine to make complex gates.
- Complex gates combine to make logic functions
- Logic functions combine to make logic blocks (like the ALU)
- Logic blocks combine to make the CPU