It’s not difficult to buy old 74x181 and 74x182 ICs on eBay. You can even get sixteen-bit ALUs like the IDT 7831 for decent prices.
Build a register file from a bank of registers. For example, use a 74x138 and a few 74x377.
Alternatively, either use a true dual port SRAM to build a three port register file, or build your own from a time-multiplexed SRAM and some bus transceivers.
Complex combinational logic can be implemented in an EEPROM truth table pretty easily.
Sometimes, part of the fun is figuring out how to build a complex device from a very limited palette of parts.