Doing relays instead is just a different device.
Well depending on the current requirement of the relay you might have to follow the shift register output with a transistor to drive the relay.
Indeed. And maybe a diode to protect the Arduino/transistor from the relay coils.
But, I think I have read somewhere that the LEDS aren't all turned ON at same time but rather only one at a time, very fast switching to the next LED (persistance of vision). If it's true then it will not work well with mechanical relays such as the ones I linked to :/ . True, or false?
I'm not sure what you mean, the relays are opto isolated so all the shift register have to do is turning a small LED ON or OFF, to activate or deactivate a relay, correct? Relays themself are powered by the 12VDC from the relay board and require 20mA each.