Arduino powered relay confusion
Your Arduino seems to be floating in relation to the other half of the circuit (Transistor, Relay, and 12V PSU).

Voltage is relative.  What this means is that when something says "5VDC" or "12VDC" its in relation to its own 0V.

When you have two or more circuits that are unreferenced to each other, there is nothing that relates ones 0V to anothers 0V. Which means that when you make only one connection, its signal is going to be for example, whatever or however they manage to capacitively couple to each other (i.e. random and erratic).

That's why you have to connect both circuits 0V. So that the 5V from the Arduino is also 5V for the transistor.

For example, if you connected Arduinos 0V to your PSUs 12V, then the signal on the transistor's base would be 17V. (assuming your USB PSU is floating in relation to the 12V).

This question on meta has some nice answers and explanations.

Please note that not everything that seems disconnected is floating: if you measure a mains connected circuit with a scope you will probably let the magic smoke escape (i.e.: explosions, sparks, etc). Your scope will be connected to your circuit through mains.