Why use a relay...it's unnecessary. A small-signal MOSFET will do. Even a 2n7000 would work here, especially it's a 5V Arduino (which you didn't specify).
Left half of the diagram applies to your case. Place a diode parallel to the fan ('load') with the cathode connected to Vdd.
As to powering the fan: you've got an Arduino and a USB adapter, just plug in USB to Arduino and connect the fan + to the Vin on the Arduino (preferably not the 5V, although it wouldn't even hurt in this case). Again, assuming the topology of a typical UNO, Nano, etc. For more accurate into, tell us what Arduino you're using.