Eg give them an area/page of the site they could manage colours, so they can add new ones. Then on a separate page allow them to choose the colours from checkboxes?
Perhaps categories is a good option. You create the categories via the control panel, then you can add a category field to wherever you want the editor to select them from (page attributes, regions, etc):
You can add more fields to your category templates, so the suggestions made in the previous comments may still be relevant to your use case.