First, you do need flyback diodes across the coils, or zeners + diodes if you need the solenoids to switch as fast as possible.
If the chips are getting extremely hot, that's a strong indication of latch-up.
This is not an uncommon situation when you combine large currents and sub-optimal layout. Chips that are connected to each other have protection diodes on the inputs and if one chip's ground bounces by more than a diode drop or two you can have large currents flowing between CMOS output and input, through the protection diodes. If that current exceeds some limit (probably in the range of 100mA for modern parts) the CMOS chip will latch up and may be destroyed if there is enough power supply current available.
The solution is to separate the high and low current paths so that the solenoid return current from the TIP emitters does not flow through the grounds on the shift registers. Connect them together at one point, usually the power supply return. The 1K resistors will prevent anything too dastardly happening if your layout isn't the greatest, but try to keep the return on the transistors physically short (low inductance). Fortunately the TIP transistors are very slow to switch so the problem isn't magnified.
If you do try MOSFETs, keep the resistors, in fact you can increase them to a few K to slow the switching.
The shift registers should not be getting hot. Even with a 5 V supply, each output only sources about 4.3 mA (check to make sure this is within the capability of these digital outputs). Times 8 outputs that's about 35 mA, which is 175 mW total with a 5 V supply. Most of that total will be dissipated in the base resistors, not the chip. Even if it was, that would only make the chips get warm.
One glaring problem with your circuit is lack of kickback catch diodes across the solenoids. When a transistor shuts off, the stored energy in the solenoid ends up going somewhere. If you don't provide it a nice and safe path, like thru a diode, then it will find a path somewhere, producing whatever voltage it takes. In this case that means creating a high enough voltage so that the transistor conducts anyway. Such a high voltage is out of spec, can damage the transistor. Doing this repeatedly is pretty much guaranteed to fry the transistor.
If you fried some of the transistors, they may be shorting the supply voltage thru the solenoid and thru the base resistor into the protection diodes of the shift register outputs. That could make them draw much more current than intended, and getting hot is quite likely.