Nick, I like your idea of replacing a blah sky with a timelapse of real clouds - I'll have to give that a try. In general, here is a technique for replacing a gray sky. It may work for what you are trying.
The secret is to use place a sky track above your footage track. Then use the Darken mode on the sky track which tells the sky layer to darken anything that is lighter in the footage track below. Since the new sky is darker than the gray sky, it will replace it. Use a mask if you have lighter objects in the non-sky part of the clip. Or, often times you can just put a gradient mask on the sky track.
If you have a solid blue sky, you might be able to use the chromakey to remove it. You can set your chromakey color to the color of the sky by using the eyedropper.
You might have to work with the secondary color corrector first to give you an even blue.