I would take a look at the technique Corinna Barber uses in these two articles:
http://blogs.msdn.com/corrinab/archive/2009/11/24/9927729.aspx
http://blogs.msdn.com/corrinab/archive/2009/12/02/9931283.aspx
Basically what she does is, at application startup, she creates a bunch of brushes (both solid and gradients) in a binding helper class (hers is called SysColors). Then she simply binds to these brushes, like so: Background="{Binding CalendarGradient, Source={StaticResource SysColors}}"
The main downside to her approach is that you have to write quite a bit of code when creating gradient brushes. And all the different gradient stops would have to be stored independently in your database (or xml or whatever). I'm thinking now that you could probably store your brushes as xaml and just use XamlReader.Load
to load the entire brush object at once. That sounds like a better plan to me, but I haven't tried this, I'm just thinking out loud.
In your situation, at application startup, you could easily load your default scheme OR pick up your color values from a WCF service or wherever. You could even implement INotiyPropertyChanged for all the brushes, and thus be able to swap them at runtime. But I guess that might give you bad performance.