Hi there,
Keying animals in motion can get expensive real quick. I have seen greenscreen footage of horses on specifically designed treadmills so the camera, greenscreen and horse do not move from their spot. Then I have also seen a project where a screen-truck drove along side a horse whilst a camera-truck was on the other side. This looked like it was quite difficult to light, and probably needed to be cleaned up a bit in post. It was done because other elements were interacting with the galloping horse so a treadmill could not be used.
If you have no budget for anything like this you may have to resort to hand keying which is never a pleasant task. Possibly parts of the key could be made repeatable with a looping matte assuming the horse doesn’t mix things up too much.
There may be other tricks to get animal keys, but the three above are the main ones I have come across.
Good luck
Alex
http://www.lightdrop.com.au