Here is how you implement your own Surrogate:
class YourCustomTypeSurrogate : IDataContractSurrogate
{
    public Type GetDataContractType(Type type)
    {
        // Just for reference
        //if (typeof(OldType).IsAssignableFrom(type))
        //{
        //    return typeof(NewType);
        //}
        return type;
    }
    public object GetObjectToSerialize(object obj, Type targetType)
    {
        // This method is called on serialization.
        //if (obj is OldType)
        //{
        //    // ... use the XmlSerializer to perform the actual serialization.
        //    NewType newObj = new NewType();
        //    return newObj;
        //}
        return obj;
    }
    public object GetDeserializedObject(object obj, Type targetType)
    {
        // This method is called on deserialization.
        // If PersonSurrogated is being deserialized...
        //if (obj is NewType)
        //{
        //    OldType newObj = new OldType();
        //    return newObj;
        //}
        return obj;
    }
    public Type GetReferencedTypeOnImport(string typeName, string typeNamespace, object customData)
    {
        // This method is called on schema import.
        //if (typeNamespace.Equals("Your Type Namespace"))
        //{
        //    if (typeName.Equals("NewType"))
        //    {
        //        return typeof(OldType);
        //    }
        //}
        return null;
    }
    public System.CodeDom.CodeTypeDeclaration ProcessImportedType(System.CodeDom.CodeTypeDeclaration typeDeclaration, System.CodeDom.CodeCompileUnit compileUnit)
    {
        // Not used in this sample.
        // You could use this method to construct an entirely 
        // new CLR type when a certain type is imported, or modify a generated
        // type in some way.
        return typeDeclaration;
    }
    public object GetCustomDataToExport(Type clrType, Type dataContractType)
    {
        // Not used in this sample
        return null;
    }
    public object GetCustomDataToExport(System.Reflection.MemberInfo memberInfo, Type dataContractType)
    {
        // Not used in this sample
        return null;
    }
    public void GetKnownCustomDataTypes(Collection<Type> customDataTypes)
    {
        // Not used in this sample
    }
}
Then you create a custom Serializer Operation Behavior :
public class CustomDataContractSerializerOperationBehavior : DataContractSerializerOperationBehavior
{
    public CustomDataContractSerializerOperationBehavior(OperationDescription operationDescription) : base(operationDescription) { }
    public override XmlObjectSerializer CreateSerializer(Type type, string name, string ns, IList<Type> knownTypes)
    {
        return new DataContractSerializer(
            type /*typeof OldType*/,
            knownTypes,
            int.MaxValue /*maxItemsInObjectGraph */,
            false /*ignoreExtensionDataObject*/,
            true /*preserveObjectReferences*/,
            new YourCustomTypeSurrogate());
    }
    public override XmlObjectSerializer CreateSerializer(Type type, XmlDictionaryString name, XmlDictionaryString ns, IList<Type> knownTypes)
    {
        return new DataContractSerializer(
            type /*typeof OldType*/,
            knownTypes,
            int.MaxValue /*maxItemsInObjectGraph */,
            false /*ignoreExtensionDataObject*/,
            true /*preserveObjectReferences*/,
            new YourCustomTypeSurrogate());
    }
}
After that, you create an attribute to apply the above operation behavior to an operation contract :
public class CustomDataContractFormatAttribute : Attribute, IOperationBehavior
{
    public void AddBindingParameters(OperationDescription description, BindingParameterCollection parameters)
    {
    }
    public void ApplyClientBehavior(OperationDescription description, ClientOperation proxy)
    {
        ReplaceDataContractSerializerOperationBehavior(description);
    }
    public void ApplyDispatchBehavior(OperationDescription description, DispatchOperation dispatch)
    {
        ReplaceDataContractSerializerOperationBehavior(description);
    }
    public void Validate(OperationDescription description)
    {
    }
    private static void ReplaceDataContractSerializerOperationBehavior(OperationDescription description)
    {
        DataContractSerializerOperationBehavior dcs = description.Behaviors.Find<DataContractSerializerOperationBehavior>();
        if (dcs != null)
            description.Behaviors.Remove(dcs);
        description.Behaviors.Add(new CustomDataContractSerializerOperationBehavior(description));
    }
}
And finally, you apply this Attribute to an operation :
    [OperationContract]
    [CustomDataContractFormat]
    void DoWork();
If you want to apply this to whole service, then you customize Service Behavior instead of Operation Behavior.
Here are the references that were used to create this example :
http://msdn.microsoft.com/en-us/library/system.runtime.serialization.idatacontractsurrogate.aspx
http://www.danrigsby.com/blog/index.php/2008/03/07/xmlserializer-vs-datacontractserializer-serialization-in-wcf/
http://www.danrigsby.com/blog/index.php/2008/04/10/specifying-a-different-serializer-per-endpoint-in-wcf/
http://social.msdn.microsoft.com/forums/en-US/wcf/thread/e4d55f3f-86d1-441d-9187-64fbd8ab2b3d/