I'll assume you can work out the variable square wave oscillator. This might be a 555 timer based design (found everywhere), though you may need to put its output into a JK FF to divide the frequency by two in order to square it up to a clean 50/50 duty cycle.
The following circuit doesn't involve an MCU (which for many reasons might still be your better appraoch.) It's just a simple bit of logic that assumes you can supply it with a square wave at \$4\times\$ the actual rate you want. The counter is synchronous and so the output should be relatively clean.

simulate this circuit – Schematic created using CircuitLab
The above system requires two D-flops (in a twisted ring Johnson counter arrangement) and two muxes (to make the twisted ring Johnson counter reversible.) Shouldn't be difficult to select appropriate logic families and then wire it up. Something like the 74LS175 and 74LS157.
If my head is on straight, setting the UP/DOWN to 0 will have A leading B and to 1 will have B leading A.
EDIT: I liked the muxes shown above better because you can get quads of them in a single IC package and because I enjoyed the relative symmetry of it. And so I avoided writing the following, earlier. I've got a moment to add the other thought in my head (not as nice, though, in my opinion.)
So, if you don't like muxes for some reason or otherwise don't mind multiple IC packages with different gate types, then you could use the following schematic instead (or any of nearby varieties of it):

simulate this circuit
This also doesn't use the \$\overline{Q}\$ output of the D-type FF. (That may expand your options a little for the D-type FF devices.) But now you can't get everything into two packages (or at least, nothing comes to my mind where only two SSI/MSI ICs might be used.)
Your call.