Frequency of a noisy signal with fixed width pulses
Not an easy problem to solve...

You could always cross-correlate the signal with a replica square wave and then apply simple thresholding to find the pulse locations. Then just count the peaks in a given interval to determine frequency.

I think the square wave nature of the signal could make the signal quite difficult to deal with in the frequency domain because of all the harmonics that comprise it.