I need 2 vcc pins on the arduino

The Arduino pins can only source a small amount of current (40mA per pin, 200mA total). You will want to use a low side switch with a transistor to satisfy the current demand of your relay. My go-to circuit for this problem is as follows (using a 1N4001 diode and a 2N3904 transistor).

^{simulate this circuit – Schematic created using CircuitLab}

I'm going to assume that the AVR controller on the Arduino board is similar to the Microchip PIC family in that the pins default to INPUT upon reset.

If that assumption is correct, all you need is a really simple sample-and-hold circuit for the relay driver. It also requires you to think about how you have your software structured.

First, I'll show the circuit. Then I'll talk about the software implications.

^{simulate this circuit – Schematic created using CircuitLab}

Software is really easy.

1) Controller is just coming out of reset. Port pins are all currently set as Input.

2) Set port pin to desired level (Hi or Lo)

3) Change port pin(s) DDR to Output

Note that the above order is important if you want to avoid glitches. If you set the pin to Output first, then set the level, there can be a glitch.

Also note that the circuit introduces a delay of about 1 ms. I assume that is completely inconsequential if you are driving a relay.

You must choose a low-leakage capacitor for C1 but that's easy. Tantalum works pretty good.