How is the frequency division using logic gates on this old video card happening?
First of all, there is a mistake in the schematic that needs to be corrected so things can start to make sense: U100, a 74LS32 IC is an OR gate instead of a NOR gate, despite what the little circle on its output may lead you to believe.

Once you fix that, inspecting the schematic you'll realize that you have a state machine where:

\$D_1=\overline{Q_4 + Q_5}\$
first bit becomes 1 only if 4th and 5th bits are both zero, otherwise becomes 0;

\$D_2=Q_1;  D_3=Q_2; D4=Q_3; D5=Q_4\$
higher bit simply follows previous state of lower bit

Having this in mind we can now create a table with all the states starting at reset state \$(Q_x=0, x=1...5)\$ as things change at each clock cycle:

$$
\begin{array}{c|cccc}
n_{CLK} &amp; {Q_1} &amp; {Q_2} &amp; {Q_3} &amp; {Q_4} &amp; {Q_5} \\
\hline
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 0 \\
5 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\
6 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 \\
7 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\
8 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 \\
9 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
\end{array}
$$

As you can see, the state machine returned to the reset state (all zeros) after 9 cycles. In addition, notice that any given flip-flop output has one 0->1 transition and one 1->0 transition along these 9 cycles. Therefore, you should see in any of the flip-flop outputs (as well as in \$D_1\$/pin 3) a signal whose frequency is the clock frequency divided by 9. 

I'm not sure why you report seeing twice that frequency (f/4.5) in the flip-flop outputs. I'm wondering if it's a result of your measurement technique that may be susceptible to glitches. It would be nice to confirm that with an oscilloscope.