Yes I think this is possible. You can basically load a new assembly at run time with the new types and then just need to have a way to get the updated type information into the service when using DataContractResolver:
http://msdn.microsoft.com/en-us/library/dd807504.aspx.
Thanks,
If this answers your question, please use the "Answer" button to say so | Ben Cline