Yes that would work although you have to drive a relay through a transistor.
rgb led uses all negative leads for the colors
No problem, just connect the anode to +5V, the red cathode through a resistor to the PWM pin. Then connect the relay contacts to the green cathode via a resistor and the other contact to ground.