Bill may not have read your requirements. The switching thresholds on the circuit he posted are vcc/3 and 2*vcc/3. That comes out to 4V and 8V in your case. Not exactly what you are looking for. Some resistive level shifting might solve your problem. Maybe Bill can design that for you.What did I do wrong: I connected the input to 2 and 6 pins (and the 8 and 4 pins to +12V and 1 to ground, of course) and the relay to the 3 output and ground but nothing happened. The relay didn't click whether the input was 8V or 12V. At one point I must have shorted another pin because the 555 became very hot.
http://forum.allaboutcircuits.com/images/icons/icon5.gif