Have I got enough pins in my Uno or should I use another board...?

Yes, ULN2803 if using Arduino outputs directly, or as buffer for 74HC595. TPIC6B595 can handle 12V directly.
Don't forget diode across the relay coil - cathode to +12C, anode to chip output.

US prices cheaper, but shipping is more?
Where in UK are you?