The simple answer is "yes". The more complex is yes, but the how to depends a bit on how this was originally shot.
If the sky is plainly blown out or the sky is evenly colored, you could try to use some of the keyng tools. This also depends on the video format you shot it as, as some keys better than others.
If there is lots of tonal range in the sky you want to replace, you'll have to add manual mattes.
In that case, you can only hope that your camera is locked down...
Probably you'll get a long way with a combination of these two.
As mentioned before, if you have a pretty even tonal sky, then using the Color Correction tools of Final Cut Pro and some patience you can probably work out a viable solution. However, if you've got a mixed sky or a lot of things going on in the sky, I'd break out the compositing tools. Take the footage into After Effects or Shake. Use the powerful rotoscoping tools in those applications and you can achieve and a seamless alteration to your sky. However, I would at that point recommend getting the assistance, in person not via forums, of a visual effects artist to do it for you so that you do attain the optimum results. Good luck.
Much faster, easier way to fix the sky without leaving FCP or using the Color Corrector.
Use the Custom Gradient Generator (Generator > Render) to create what is pretty much a Gradiant Poloarizer filter in post. Align it so that the dark part will cover the sky and the gradient to white sets where you need it. This will go on the video track above your clip.
Once there, right click on this Generator clip and select Composite Mode > Overlay.
Tweak as needed (poisition, gradient, opacity), done.