Long before I ever touched blender, I played with Planetside's Terragen. Able to create terrain, clouds, skies, beautiful worlds with the touch of a button. Unfortunately it does not work in linux too well...
I've been looking for an alternative to create skies, clouds, just worlds in general. I've found two alternatives, that don't seem all ready, but interesting to look at.
Geomorph - Appears to be a relatively simple height field terrain generator, which you can then import into blender. But this doesn't create the skies and the worlds I want.
Picogen - Looks like it's a better tuned alternative, which can generate skies and worlds. Although the author states that the cloud generation isn't fully ready.
If you know of others let me know, this was a quick search, and I haven't even used them yet.
I'll keep looking around, but I really would like to say the future looks promising. I'll eventually find something and create a tutorial about how to use generated skies in blender. For now, cgskies.com is a great place to get free skies for use in your simple personal use scenes, you can also get skies to use for a fee, higher resolution than you can get for free.
If you do want to use and pay for a sky from cgskies.com I suggest downloading the free trying it out in your scene first, then pay for the one you like.