What values / components do I need in this flip-flop circuit?
R6 and R7 are to pull the base to ground when the transistor is off. The circuit would probably work without them, but it's good to work with a known value.  
I would start with 1k&Omega; for R1 and R4, 10k&Omega; for R2 and R3, 100k&Omega;-470k&Omega; for R6 and R7, 22k&Omega;-100k&Omega; for R5 and R8. C1 and C2 can be 100nF (probably anything 10nF - 1uF will be okay)
Yes, any small signal diode and general purpose NPN should work fine.
Yes, 12V is fine.
Yes if you get the values right. You could replace one of the load resistors (e.g. R4) with the coil and reverse diode, this would probably work okay if the drive current isn't too high. Since the switching will happen on the negative edge of the pulse and depends mainly on the negative edge being fast enough and dropping low enough to pull the base down, the circuit should be pretty flexible value wise (just make sure it doesn;t have to work too hard against R2/R3, and the cap is large enough to allow enough of the pulse through)
The other option is to use higher values for R1/R4, and use the output of one to drive a MOSFET which switches the relay.    
No I don't think so, the switch should be clean electrically (any mechanical bounce is due to the relay itself)


With something quite simple like this, just building the circuit and tinkering with the various values, examining with a scope to see how changing x affects things will quickly give you a picture of how it works and the optimum values to use for your application. You can simulate it too of course, which I advise also (I am a big fan of SPICEing stuff as you may have noticed), but it's a bit more fun to mess about with real components ;-)