I added team colour on a couple of other units (firebat, civilian hellion, etc) and it worked pretty well. Actually, since the Marine's textures are so close to the Tychus/Raynor ones, it would even be easier.
EDIT: Just tested adding team colour on Tychus and it didn't work. I guess it just doesn't check the alpha channel for team color. Odd.
One is change the whole model's tint... This adds the color to every portion of the model (see Color TD) This isn't what you wanted from your discription...
Two is to export the texture, find the channel they use to determine "team color" and recolor the texture by yourself (or have someone else do it)... don't recomend this.
Three is to pick a new model.
There MIGHT be some special flag set in his model file that changes portions of him to "team colors" but that is highly doubtful. The texture artist for the heroes probably was given specific colorschemes to use.