FM doesn't shift frequency over distance. Temperature and a few other things can affect frequency, though.
As an example, the shift in frequency of EM radiation from stars (some at the radio frequency) can be accurately used to measure the relative speed of the object over interstellar distances.
I may be mistaken, but i remember that a blue shift or red shift can occur because of the movement. But since the composition of stars can be predicted with a reasonable accuracy, the redshift or blue shift is accounted for. Indeed you are right, because the redshift or blue shift is used to determine the speed of the object. Just as the Doppler effect if i recall correctly.
For those interested :
A star made up primarily from hydrogen, will radiate EM at a specific known wavelength. The deviation of this wavelength because of redshift or blueshift is used to determine the speed.
Of course, gravitational effects are evened out. Or in some occasions used as a means to discover interesting phenomena in space.
http://en.wikipedia.org/wiki/Hydrogen_line
EDIT:
Of course there are interesting theories with accompanying research that we might be off in some occasions when it comes to using hydrogen spectral lines to determine distances and dimensions in the universe.