Opposing Force never changed skies. They used the different-sky-per-face method. You could only see one side of the sky, so they changed the player's orientation in the plane to face a different part of the sky. Take a look in the GFC and you'll find a sky set with inconsistent textures.
Really, you've only got a few options, and I doubt you'll like them.
1: Use Zeeba-G's method and cover the sky with different additive textures to change the sky's tone.
2: Convert the TGA files to a wad, and build a cube textured with the converted sky(stretched to fit each face) around the very edge of the mapping grid. This would be the closest looking to a real dynamic skybox, but it will kill your vis compiling time. You would also have to manually null off every face that would normally be facing the void. But there are so many problems that could arise from this, if not done correctly, that I wouldn't even bother. Especially when you could just as easily...
3: ...Use a model with a sky texture applied to it that is big enough to span the entire mapping grid, or more, much like my 3D Sky example map. This is easily the most optimized method, but you have to make sure that VIS can see the model from any given point in the map, otherwise you will end up with areas where the sky model doesn't get rendered. If the playing area is relatively small, or relatively open, a sky model would be your best bet. If you want, I can make you 4 sky sphere/cube models to use.