You need a pin that you can control, right?
None of the power pins will work for you. You need to use one of the I/O pins.
In a way, this is simpler. You can power the relay with a 12V source (battery, adapter, whatever) and not need to worry about drawing too much current through the Arduino.
But in a way, it's more complex. You can't just hook the relay up to the board directly, you have to turn it on with a transistor or FET. Like in this example from the playground: Arduino Playground - HomePage
This is the circuit I would try. But a different NPN transistor might be okay for your relay (solenoid in the schematic). But I'm not the guy to pick your transistor. I tend to pick randomly and blow them up.