Yes, the 2N3904 should work OK. Most any diode would do ... IN4448, 1N914, IN4004, 1N4005, 1N4006, 1N4007 and others.
Does the downwards arrow mean to ground, except we do not want the arduino and the 5v to have common ground?
for any diode, this is the anode side -----l>|------ this is the cathode side
The long line side does not mean "to ground". In this application, this end of the diode (cathode) connects to the center pin of the relay coil (+5V).
you have provided the diagram for a single latch relay. Will the same script and circuit work for the double latch?
No, it's for the double-winding Latching Type.
You may have a different relay contact configuration. The SPDT (single pole double throw) type "1C" (form-C). Yes, it will work for this type also.