Trapcode's Horizon will give you a camera-aware background, but it won't actually generate the sky automatically. You could set up a comp with the kind of gradiated color you want along with cloud movement etc. and use it with Horizon.
If you have it, Cinema 4d has an tool that you can use to generate skies. You can even base it on a location in time and space.
- The Great Szalam
(The 'Great' stands for 'Not So Great, in fact, Extremely Humble')
No trees were harmed in the creation of this message, but several thousand electrons were mildly inconvenienced.