Wouldn't the relay coil still need power to stay latched?

Depending on what you meant by "after power is removed". If the 12 volt supply is always ON and power is removed through a switch then the mosfet idea can work.
Like this:

 

Depending on what you meant by "after power is removed". If the 12 volt supply is always ON and power is removed through a switch then the mosfet idea can work.

In my case, the power is removed altogether.

 

I have one of those relays, 5mF will get you 3 seconds.

Can you do a quick experiment for me? I just remembered that when I turn off power to a mains (AC) to 5v/12v DC power supply, they normally still have some charge in them and are able to drive an LED for a couple of seconds. I was wondering if you can connect 12v power supply to this relay, plug it in to mains voltage and then unplug it, roughly how long is it able to keep the relay latched?

 

roughly how long is it able to keep the relay latched?

Not very long. There is a big difference between the load current of 1 LED and your relay. And, there is an unknown difference between the output filter capacitor sizes of some unknown supply and yours.

ak

 

But R1 is supposed to be 22ohm and current would be closed to 500mA while capacitor is charging - which will take 500ms, then just 30mA to keep relay latched.

So what? Why do you think that affects the resistor chosen for the LED (it does not.)

My point is that you don’t need to waste 20mA on an LED that will be blindingly bright.

 

So what? Why do you think that affects the resistor chosen for the LED (it does not.)

I was talking about R1 (for Capacitor) but it seems you were referring to R2 (for LED).

 

Can you do a quick experiment for me?

Not long as ak mentioned. With my supply it was almost 1 second with just the relay connected.
With this circuit it was right at 2 seconds. YMMV.

This modification using the mosfet circuit with a battery backup works but probably not practical for your application.
With the component values shown the delay was appx 3 seconds.

 

Thanks @sghioto! I should have parts delivered by tomorrow and will be able to experiment myself as well.

 

Thanks Everyone! I got the components and was able to get it to work.

Regarding power supplies, I had 2x brick-type power supplies (12v 5a) and 1 wall-type (12v 2a). I tested the circuit with all three and noticed that 5amp supplies had plenty of power reserve and were able to keep the relay latched for 10+ seconds. The downside was that they took 500ms or so to supply output power when they were plugged in. OTOH, 2amp wall-type supply was able to output power near instantaneously, and was still able to keep the relay latched for 2+ seconds (with the LED, so probably 3-4 seconds without LED).

I was able to get the desired result with 12v 2amp wall adapter/power-supply. Just need to fabricate a pcb now and finish it off.