A circular polarizer can darken just the sky, actually. I used that to my advantage a while back. I locked the exposure for my foreground, set the CPL to it's "darkest" setting, then took the photo. The sky turned out looking "normal" (i.e. it was a light blue sky rather than a very dark, vivid blue).
Anyway, what I would recommend is that you shoot in RAW mode. After that, set the exposure as you did previously, but set the exposure compensation to between -2/3 and -1EV. After that, open the image up in Photoshop/Gimp/Paintshop, and adjust the Curves until you're happy.
Best of luck getting that shot!