Just dropping in here.
Maybe it's an idea to have an 'overlay' for every ship, which can be changed in colour, rather than the hulls themselves?
Spoiler
(http://avatar.home.xs4all.nl/crap/bashbash.png)
E.g.
Spoiler
(http://i44.tinypic.com/2iub7sz.png) (http://i41.tinypic.com/neujcz.png)
Not Perfect, but its simple and can make quite a difference. I just think that even if the society has collapsed people will want to paint their ships.
Okay, so I messed around, cut bits off of ships and recoloured them, trying to keep the shiny metal bits intact, but this can be a good case for colouring zones.
I am not a pixel artist, and did nothing but a little cutting and recolourising. I cut bits off, and put them into layers, which means I can recolour them as many times as I like. I thought about taking each panel of the medusa and making each have its own colour, but I didn't want to stare at a screen that closely for that long.
I tried to upload them to imgur, but it wouldn't accept.
I made a poor attempt to "piratise" the Apogee, and decided to show how creepy the Medusa really is. Okay, seems the apogee is too large to attatch as a file, and imgur won't accept them, so... here's the medusa.
I have attempted to do the same a few times, however it was with some kit bashes i did. The same effect sould be easily applied to stock ships though. It's quite effective as a lot of the ships have distinctive panels (especially the tach ships). Here is the paragon i did real quick, and the more detailed kitbashes. Changing the hull shade and colouration can have a massive impact, and may take away from its identity, however it creates a new one.
Spoiler
(http://i43.tinypic.com/6suxle.png)(http://i43.tinypic.com/2vbwhtz.png)(http://i41.tinypic.com/546ro4.jpg)(http://i41.tinypic.com/352jh95.png)
I understand that these are far too off track from what we're talking about here but the concept can be carried over, that is, the colourisation of panels of a ship. The most realistic approach is most definitely the decal overlays mentioned by Gotcha! But you can achieve some really cool stuff just by messing around with hue sliders and layers.
I think each ship could be divided into any number of zones (main hull, secondary hull, decals, machinery, etc.etc. which can then be separately colored (kinda like how ME2-3 did with shep's armor, or how DOWII did with their army customizer, or how HWII did with their ships albeit a bit more sophisticated)
Actually, if you could do that, then you could probably set up a "fleet scheme" option that colours all primary/secondary/decals/stripes/etcetera accordingly, which would then apply it to all ships in your fleet, preferably just slapping the template on the ships at hand, allowing you to further customise any given ship beyond that.
Edit: Okay, got imgur to work.
Spoiler
(http://i.imgur.com/4gvFt8t.png)