Choosing external adapter voltage to power Arduino & Relay
tl;dr 9V or 5V adapter, Arduino powers a 5V latching relay

If the load isn't going to be switched very frequently, you should go with a latching relay. Actually, the only proper use for a non latching relay is in a device that switches to one state (on or off) occasionally, for short periods of time. If the device isn't switched more frequently than once in a couple of seconds, go with a latching relay.

If you use a single-winding latching relay, you can connect its coil to 2 digital outputs and set them to input-high-impedance when the relay is in a stable state. When you want the relay to switch over to one position, you pulse one of its coil pins with high, and the other with low for several milliseconds (look at the datasheet). If you want the relay to switch the other way, you do the opposite - pulse the other one high, and the first one low.

The actuation voltage has nothing to do with the voltage or power that goes through a relay. There are no advantages to using a 12V relay, and you'd need an external driver for it (or at least a transistor / darlington pair). The solution I proposed above, with a 5V latching relay, is optimal. Just put two diodes in reverse parallel across the coil to prevent collapsing-magnetic-field-induced voltage spikes from damaging your Arduino.