Have you got reason to believe this measuring technique is feasible? I don't think you said what altitude range you need to support, but Wikipedia says that the speed of sound drops from circa 340 ms-1 at sea level to circa 295 ms-1 in the 11,000 - 20,000m altitude range and then rises slightly up to 29,000 m. So the speed does vary with altitude, not by a huge amount and not in a linear way. At sea level the propagation time would be about 1ms and it would reduce by about 100 us over the entire altitude range. I don't know how much resolution you expect to get over that 20,000m range, but I suspect that the resolution you are able to achieve based on measuring variations in the sub 100 us range will be rather poor.
I'm not convinced the frequency detection approach you describe makes any sense. If anything, I would have thought you needed a hardware phased-locked loop to have any chance of detecting the presence of your signal, and just looking for changes in a binary signal in a noisy environment seems to me to be utterly futile. Even supposing you get it working, what you'd be measuring is the propagation time plus the signal acquisition time where the acquisition time is unknown and varying. Using FFT suffers from the similar problem (that it only works on the basis of a sample over an interval) plus requiring high speed analog-to-digital conversion and the ability to process a significant data set, which is not something Arduino is really well suited for.
If you want to measure the speed of sound, I would have thought your best chance was to implement a conventional ping sensor and arrange for the amplitude to be high enough to be reliably detectable within the range of conditions you expect to encounter. I think that what you'd really be measuring, if you succeed, would be temperature. In that case I wonder whether you might not be better off just measuring temperature and/or pressure and calculate the altitude from that. However, I know that this problem has been solved many times and no doubt you know of, or will be able to find, somebody who has found a workable solution. In that case, I suggest you try to copy it. 