Here are the problems you are going to face. Natural red hair is very close to skin tone so a procedural matte is going to be tough to pull off. There are other "red" hair colors that may work to create a procedural matte. Procedural matte means taking information from a color or luminance channel and using that information in some way to create a matte. This includes things like keying or the change color options or other options. Depending on how the image is lit and what color the hair is you may have some success getting started with the procedure but you're probably going to have to do some rotoscoping and refining edges.
A good place to start to look for solutions would be to research changing hair color in Photoshop to discover techniques for changing color that will work and then figure out how you are going to create a matte for the hair that works well enough. You might want to look at this good tutorial on how to change hair color in Photoshop (not embedded because it's not an AE tutorial):How to change hair color in photoshop cs6 tutorial - YouTube
Take a natural redhead like the girl in this example:
I could not find anything that worked well to create a procedural matte so I tried Rotobrush and got pretty close to a decent hair selection in a few minutes.
The roto is used for a track matte for an adjustment layer with Selective color enabled.
It's not perfect by a long shot but it shows a great example of the problems you will be facing. If you care to post a screenshot or a sample of the video I can make some additional suggestions. There are about as many ways to go about something like this as there are redheads.