How can a 74LS76 JK Flip Flop's outputs Q and Q-bar not be fully complementary?
Indeed this was a bad chip! It functioned almost perfectly fine, no issues except the switching was not right. I went and bought another one for an eff-ton of money 4 USD -- twice the price of a kilo of strawberries -- and behold:

Note how much more smooth the traces are. Not that it would necessarily matter, but clearly it behaves differently than the first chip.
This new one is also a TI make, but looks nicer. Not sure if the other one was a Chinese fake?