Well, one thing you probably can change real easily is the color of an existing skybox...for example, let's say you don't like the "green" skybox...you can just recolor the texture to make it more "blue" or "pink" or whatever color you want...and in a program like photoshop, usually recoloring or changing the hue/saturation of an image is quite easy...
Downside is, you won't be able to add new color schemes, only change an existing skybox...if you truly want new skyboxes I don't know what to tell you...Nova's Novus Universom has a new skybox (more classic black/white starry sky) but it's distorted near the poles...GoaFan's Enhanced 4x Mod I think has a recolored skybox (or maybe several) but I'm not sure....