Changing the tempo of a song always requires re-sampling. Speeding up or slowing down is simply done by reducing or increasing the space between individual audio samples. That also changes the pitch, since the heard frequencies will be higher or lower.
Now, if you want to change the pitch (that is, keep the original) of a tempo-stretched/squeezed song, you will actually have to touch the content of the samples and pitch-shift it. This means decoding, processing, and, consequently, re-encoding to a file.
So, to summarize, there's no way around re-encoding, unless you can do the time-stretching live, during playback.