Programatically building a skybox

I'd like to be able to create a skybox programatically, with stars etc showing based on where one is in space (as seen in Elite).

What are some possible ways to do this? The obvious approach that occurs to me is creating the 6 skybox textures by hand, which would require mapping a spherical texture into the 6 textures of the cube, which may be computationally expensive.

Are there shader based ways to accomplish that that would be simpler or faster?

Getting more interesting - I'd also like to be able to do something fancy, like say someone goes to warp speed. Slowly the starfield would change. You could probably make a nice effect by preparing the next starfield box, and 'morphing' from one skybox to the next. How might that be accomplished?