I can't find any suitable divide-by-two circuit...

So I have to go back to the Earle flip flop and loop it back on itself.

src: https://en.wikipedia.org/wiki/Flip-flop_(electronics)#Classical_positive-edge-triggered_D_flip-flop

And indeed, it works great with Falstad's CircuitJS:

(source)

That's 6  transistors, at least.

I don't know how fast it can go but at least it's not dependent on a capacitor's value.

Now, how would it work with NORs ?

Well just replace the NANDs with NORs !

.