Yeah, solderless breadboard is pretty hopeless for high speed. It has bad parasitics of all types: parasitic capacitance, parasitic inductance, leakage currents, contact resistance, and crosstalk. You can prototype a lot of stuff on it, but if you are trying to go for high speed you will be completely dominated by the breadboard. An etched copper clad board or a well done perfboard will be much better.
Another big issue is the off-board wiring. The maximum toggle rate is basically limited by the capacitance you have to charge. The device has a certain internal capacitance that gives you a baseline, but anything you add on top of that will slow things down. 30 cm of twisted pair wiring will add about 20 picofarads of load. You can get around this by using transmission lines terminated in the characteristic impedance, but many logic gates don't have enough output current to drive a 50 ohm coax. One trick is to use a hex inverter with 3 gates wired in parallel. They will have no problem driving 50 ohms, although you need really good supply bypassing here.
You will have the same problem with the input signal, depending on your signal source. Function generators will be designed to drive a 50 ohm terminated transmission line, but do you have one fast enough?
So what I would recommend is to make a small PCB with a ring oscillator (an odd number of inverters connected in a ring) with the output then connected to a ripple counter used as a divide by 64 counter (i.e., tap the 6th bit). You can now measure with a cheap scope or frequency counter how the supply voltage affects the oscillation frequency. That will basically be related to the propagation delay through the inverters. You can then dunk it in liquid nitrogen and see how the output frequency vs. voltage curve changes. This won't necessarily tell you the fastest toggle frequency possible, but it should tell you if the device gets 10% faster. Since the only signal leaving the board is the DC voltage and the divided signal that is < 10 MHz, you should have no problems with cable loads.
It may take some experimentation. You might need to use a separate fixed supply for the frequency divider and a variable supply for the counter. You might need to capacitively couple the signal (you will then need a voltage divider to bias the voltage to the counter at mid-supply). You might try mixing logic families: for instance put a 74AC series ring oscillator with a 74HC series counter.
Record what you do and let us know the results.