Since my signals are close to squares, could I send them through the digital pins (2,3). How would I handle the interrupt if now I have two different signals that I will need to compare?
The answer to the first question is yes. But, I wouldn't. I'd use 4 and 5. Or use 2 and 3, but attach interrupt handlers to the two pins (they are the external interrupt pins). Each ISR would fire on the RISING edge or the FALLING edge. In each ISR, record when the interrupt occured. In loop, look at the relative times.