Insta is right, a 555 is simple to setup for this and costs less than a dollar. I was thinking you were including something like the 555 in your considerations, but just in case here is a possible transistor only solution (parts shown and values are guidlelines, circuit is rough and could be improved, but it's gives the idea - time will vary with components chosen, so you may need to tweak things a bit, add a pot instead of the R1/R7, etc) 

Circuit:

![Power Off Relay Drive][1]

Simulation:

![Circuit Simulation][2]

L1 is your relay coil, and is powered for roughly 60 seconds on the 12V supply dropping out. C2 may need to be increased if the +12V supply drops slowly. 

**555 Solution**

Here is a version based around the trusty old 555 timer IC:

![555 Version][3]

Depending on how fast the 12V supply drops, you may need to increase C3 (if it drops slowly) Again values are guidelines, you can tweak as necessary. The R3/R4 divider stops the voltage going negative at the trigger input, which might cause issues. 
The diode (D1) can probably also be included in a similar fashion with the first circuit (in series with R5) to stop the power on pulse you mentioned (you would also need a large value resistor from the input side of C2 to +5V) 

Simulation:

![555 Version Simulation][4]


 [1]: https://i.sstatic.net/MYODu.png
 [2]: https://i.sstatic.net/Z9DVl.png
 [3]: https://i.sstatic.net/syzYb.png
 [4]: https://i.sstatic.net/N8FGj.png