Assuming you clear one port before shifting the bit along the other, it should only drive one relay at a time. Please show yur schematic because it sounds like you may have a problem with either the power source as the relays switch or back EMF upsetting the port pins.
To operate only one random relay at a time, the easiest way is to build a 16-bit shift register out of two 8-bit variables, initialize it to 00000000 00000001 then left shift it a random number of times so the '1' ends up in a new place. Then output one variable to each port.
Brian.