These circuits assume 3 logic states: 0 (GND), 1 (=relay activation voltage), Z (high impedance). The 0 and 1 should be able to source and sink the current  of a number of relays (limited by relay contact current). Relay settling time is represented by the letter T (e.g. 10 ms, maybe slower for pre-1940 relays). Pre-1940 there were no reliable diodes, so relay coils should have a circuit of R and C in series across it to damp voltage spikes. As a guideline, use an R of the same value as the relay coil DC resistance, and a C of 10 nF. This RC circuit is not shown in the circuits.

Circuit drawings done using Kicad, simulations using circuitjs1 (Kicad's spice doesn't have relays), load a selected simulation file in circuitjs. Not all circuits might have simulation files.

circuitjs1 offline use: https://www.falstad.com/circuit/offline/

circuitjs1 online use https://www.falstad.com/circuit/

Clock generator

Choose R1 so that the relay reliable engages.
R2 is ideally such, that the parallel resistance of the relay coil and R2 equal R1. In the example, 1500 parallel with 700 gives 477 ohm.
R2 determines duty cycle (within limits), I got 75+85 ms per cycle. Different relays will need different component values.

C1 determines frequency, in my test I selected for 6 Hz. Lower C1 values give higher frequencies, but the relay switch time becomes a larger part of the total cycle time.

A third set of contacts on the relay would enable an inverse clock too, possible with some dead time between the two due to relay switching time.

With another relay one could at selected times add Cs parallel, to lower frequency, when a slower clock is desired e.g. for a slower circuit. Such a C should always be connected to GND at the minus side, and permanently fed at the plus side via a high resistance value (say, 1 M Ohm) from a voltage equal to the lowest voltage on the relay, to prevent wrong pulses when it is switched
parallel to the existing C.

Latch with clear

This 2 bit latch uses the fact that the hold current of a mechanical relay is lower than the activation current. VDC is the relay voltage.

Choose R1 and R2 so that the relays reliably holds. In my tests, with 24V/700ohm relays, 1k2 ohm gave the minimum hold voltage according to the datasheet, but my relays held fine with 1k8 too. It saves considerable energy too, when in hold mode.

If the "write" relay is activated, input data (here D0 and D1) is connected to the associated latch relay. If the input is VDC, a latch relay will be activated if it was not, otherwise it stays activated. Once activated, it stays activated if K1 is de-activated because of the R. During the latch relay activate time there will be a current from VDC to GND which is higher than the normal relay current (because of the R), but it lasts only a short time until the normally closed contact starts moving.

If the input is GND, and the write is activated, a latch relay will get 0 volts across it and is de-activated.

This circuit can be expanded to as many bits as required.

Propagation time: input-to-output: 2 T, clear-to-outout 1 T.

D-flipflop with clear

This one bit D-flipflop uses two latch circuits in series, separated by a clocked relay. A latch works fine for just storage, but if the output might need feedback to the input, a separation in time is needed.

Propagation time: input-to-output: 4 T, clear-to-outout 1 T.

For the latch details, see the latch circuit.

Program counter

Per bit, a D-flipflop in divided-by-two mode, which each flipflop clocked by the output of the previous bit. With an extra relay to allow setting the counter to a selected value (when a jump in the code occurs).

Propagation time input-to-stable-output: 2 + 2 * number of bits T.

For D-flipflop details, see the D-flipflop circuit.

If you run the simulation (counting only) with circuitjs, at slow speed you can clearly see the propagation delays. The simulation has 3 bits, with LED added for clarity.