At such large stretching factors, you can generously ignore phase information of the source signal and also assume the signal to be stationary.
What you can do is use a windowed short time FT to analyse a single frame, take the magnitude of the Fourier coefficients and smooth them to get an approximate spectral shape for the current frame. For synthesising a stretched signal you can just feed white noise through a convolution with the smoothed spectrum to get a stationary signal with the right spectrum.
The length of the noise signal for each frame determines the stretch factor, and fading between the resulting signals of adjacent blocks will give you the impression of an evolving sound.
Make sure that the noise is uncorrelated between frames, i.e. don't use a pre-calculated noise vector.
If you want to process stereo signals, it is probably best to first decompose the stereo signal into its mid and side channels, stretch those independently and convert back to left/right.