What would be the best way to go about things if I only have 12v and no voltage regulator handy?
Give up and go home and stop destroying perfectly good components.
Alternatively you could use the 5V that comes off the arduino's 5V regulator line when the 12V is connected to Vin.