I wcf data service sono normali servizi wcf esposti in http che personalizzano solo alcuni aspetti, perciò credo che tu possa usare un IDispatchMessageInspector (se ti serve lato server) o IClientMessageInspector, per controllare nelle Properties se è presente una proprietà di nome HttpRequestMessageProperty.Name. E' di tipo HttpRequestMessageProperty e la puoi modificare per inserire gli Headers che vuoi.

Con IClientMessageInspector automatizzavi il tutto ma va bene anche così