I tried the SN754410 over the weekend and it wouldn't drive the solenoids (Common 12V and using the SN754410 to give a low signal to each of the 4 solenoids). I measured around 20 ohms with a multimeter. But regardless running two at a time wasn't working with this chip. It powered the leds just fine(had leds connected to the output of the SN754410 so I could visualize that it was working).
This is why I recommended using mosfets. However, a high-gain low-saturation medium-current BJT such as the ZTX851 would also be suitable for switching 0.55A.
Edit the chip actually does work. The LEDs were not getting juice because I had a 1.5k resistor in series (12V) and the solenoids were taking all the power so they weren't lighting up. But the solenoids are working just fine.