Don't be afraid of SMD, it's really not so bad.
But: you sound like someone who will be happy to learn about serial in, parallel out shift registers (which happen to exist in the form of LED drivers). That's the classical way of extending the number of IO pins for any device that you can switch two IO pins, or even easier, for any device that has an SPI controller. You'd probably really want to use three pins: one (called MOSI in SPI speech) for the data (on/off), one for the clock (when the IC "reads" the data, SCLK) and a separate one to let the shift register know that all data has been transmitted and the new LED configuration can now be used ("Latched"). You can omit that third pin and just connect the latch to the clock pin, but you might see flickering then, during updates.
You can buy the LED driver I linked to for 2.16€ at Arrow, which happen to ship for free to Denmark.
The TLC6C598 is cheaper, and can quite possibly also be requested as an engineering sample, seeing that you seem to be developing a rather interesting device.
Both devices' usage boil down to this schematic:
The greyed-out part is when you need more than 8 LEDs, you just "daisy-chain" these registers, and can address arbitrarily many LEDs.
These LED drivers are really just shift registers with a slightly beefier output stage; you should be able to drive relays, if they use less than 50 mA.
If your relay needs more current, use a bog-normal 40ct shift register, and use it to switch NPN transistors, which switch the relays. That way, your shift register only needs to have enough current sourcing capability to drive an NPN transistor's base.
If you decide to go for optocouplers, pick ones that have low enough current so you can use them with standard shift registers. There's probably even shift registers that include optocouplers! Shift registers are really everywhere in digital circuitry :)
Another different, but very easy method:
Use I²C as protocol to communicate with an I²C port expander (example); I²C only needs two pins (but requires that you have an I²C controller, but that is pretty standard.