i think microcontroller is easiest if it is an option, then all you need is voltage divider resistors, and rectifier circuit on each 120v line (if its not dc already)
otherwise like i mentioned earlier, you are looking for a flip flop to toggle the led,
since you DO NOT WANT TO CONTROL THE SWITCH, and just detect a change,
\
there maybe a way to make a flipflop toggle the led ... plus then you would need more ff's to store the old state and new states, , then some AND logic to compare the difference between states, and triggers re-store the new state and do the toggle, but again that circuit could get a bit complicated ...