A number of issues.
In the first circuit, of course, the capacitor should be
simulate this circuit – Schematic created using CircuitLab
Just as importantly, don't get hung up on the value just yet. Its' value is determined by switching speed of the switch, and the allowable droop in voltage when there is no source connected.
Using a mechanical contactor for switching a DC current is generally a bit tricky. The problem is that, unlike AC, when you try to break a current flow an arc will develop between the contacts, and without the voltage reversal inherent in AC, the arc can persist and damage the contacts. DC contactors do work around this, but they tend to be expensive. (Actually, contactors in general tend to be expensive, but you probably already know this.) Solid-state DC relays are probably your best bet if you want to go the contactor route. Digikey has some 160 amp units. For $150 +.
Going MOSFET is probably your best choice, and for this application you need a p-type high-side unit configured like so
simulate this circuit
And you're in luck. The MOSFET I've shown is available from Digikey for $25.
M2 is almost any n-type with a voltage rating greater than 50 volts.
I show the input drive as 0/5 volts. If you must use a lower logic level (like 3.3) that's certainly possible, but you must remember to get "logic-level" MOSFETs, since otherwise they may require 4 volts to turn on fully.
This circuit ought to be easily capable of 1 usec switching. That means that you will have to learn the fine art of protecting against inductive surges, but that's a story for another time.
You'll also note that this circuit does not require a separate "contactor" supply. If, for some reason (like you can get one for free) you decide to go the contactor route, note that you don't need a separate supply for it. You just use the battery you're switching to drive it.
You can use two of these circuits to create a double-throw effect, but you have to make sure that there is a delay between releasing one before activating the other. The delay should be on the order of a microsecond or so, but check your actual circuit operation first.
You are going to need an interposing transistor driver between the microcontroller and the relay.
There are two reasons for this:
1) Your relay coil takes more current than the microcontroller can supply.
2) The output voltage of the microcontroller is either 0V or 5V. The bottom end of your relay coil has 12V on it when it is not pulled to ground.
You don't need an optocoupler unless there is a need to electrically isolate the controller power supply from the relay coil power supply.
simulate this circuit – Schematic created using CircuitLab
The above assumes that you are using a relay with built-in flyback suppression diode and the top end of the relay coil is tied to your 12V power rail.
Note that the ground of the 12V rail is tied to the controller ground.
Best Answer
If the circuit on the target device does not require too much current to trigger, using an optocoupler will probably work fine. Here's the pinout of a fairly typical optocoupler - 4N35:
Arduino gets connected to the pins on the left side, the target device is connected to the pins on the right side. You are correct - the two devices should not share a common ground.
On the Arduino side, wiring and controlling the optocoupler is as simple as wiring and flashing a LED. You just need to place a current-limiting resistor in series with either the anode or the cathode. For example: PIN -> R_limit -> Anode ... Cathode -> GND. Resistor values between 330 ohm and 1k ohm should be OK.
At the target device, the collector pin is connected to the node with higher voltage and the emitter pin is connected to the node with lower voltage. When the optocoupler is activated, the transistor at its output starts conducting, effectively closing the circuit.