The problem with a capacitor across Q1 is that it will get shorted by Q1, and that's bad for Q1.
You could try placing a capacitor between Q2's base and emitter, with a schottky diode reverse biased across R2. This will prevent Q2 turning on immediately the power is applied (giving an initial pulse), but allow it to turn off reasonably quickly (assuming there is a low impedance across the power supply when it's off.
The issue here s that while you will get a pulse on power on and power off, there is no simple way to ensure that your relay stays correctly in sync (i.e. what if it gets into the wrong state?)
You could try placing a capacitor between Q2's base and emitter, with a schottky diode reverse biased across R2. This will prevent Q2 turning on immediately the power is applied (giving an initial pulse), but allow it to turn off reasonably quickly (assuming there is a low impedance across the power supply when it's off.
The issue here s that while you will get a pulse on power on and power off, there is no simple way to ensure that your relay stays correctly in sync (i.e. what if it gets into the wrong state?)