Relays take lots more power to pull in than to hold in. If you have a big capacitor, so that 12 V is there to pull it in, you could drop to 4 V or less once it has pulled in. A small relay like that will only take 50 ms to pull in, and I guess that you could get away with a capacitor of about 4700 uF. Also a 12 V capacitor will not be damaged by a much larger voltage for a few ms, so it would be fine to charge a capacitor to 30 V or so, discharge that into the relay, and then hold 50 mA or so to keep the relay on. If you are charging to 30 V, you will only need 1000 uF or so.
Make sure you have a zener diode to protect the capacitor from too high a voltage when the relay is off.