You WILL need to use millis() timing. This tutorial shows how its done for flashing 2 leds. You can easily adapt it to work 2 solenoids.
also read this