I think using a 'logic level' N-channel power MOSFET as a low side switch is the best solution overall. As long as you have a diode across the solenoid coil terminals you shouldn't risk any damage to the arduino just because you have the 12vdc negative terminal wired to a arduino ground pin.
Lefty