Best setup for 12v solenoid

MrGarak:

  1. Two separate power supplies are needed, a 12v one for the solenoid, and the arduino one. I don't want to use the 12v for the arduino because the vreg will get very hot.

No, you can use a single power supply. The regulator will not get hot unless you draw a lot of current from the +5V pin of the Arduino - in which case, either use 2 supplies or use a 5V switching regulator to derive 5V from the 12V supply.