Phase shift just with a logic gates
The preferred way to perform such task is by using phase-locked loop (PLL), which is not a solution with only logic gates though. So this only partially solves your task in that it doesn't use a microcontroller. However, from the context of your question I will assume that FPGA-based implementation also suits your needs and most modern FPGAs have some kind of PLL on a chip.
You will need a PLL with a dynamic phase shift feature. For example, in Intel FPGA PLLs:

The dynamic phase shifting feature allows the output phases of
individual fractional PLL outputs to be dynamically adjusted relative
to each other and to the reference clock. The smallest incremental
step equals to 1/8th of the VCO period. The output clocks are active
during this dynamic phase-shift process.

Depending on a particular FPGA this option can be not present at all or can be limited. For example, this FPGA's PLL from Gowin allows dynamic phase shift, but doesn't have inputs to change a phase shift direction.
Another option is to use a DLL, for example DLLDLY module in Gowin's FPGAs allows some form of phase shift.
Third option, based on the stated 20Hz - 1kHz frequency range, may be using a system clock with higher frequency for desired phase resolution and with the help of counter-dividers with adjustable starting values. This will be a fully digital solution, but not &quot;frequency independent&quot;.