OK, I am a fucking retard. Actually all my mistake here. When people walk (unless they walk really funny, or you want something super cartoony, or a sneak or whatnot) walk at an even speed and this means that the head is spaced equally, the feet are NOT.
I made a new gif, which should please robotacon and Ben.
This is made properly, the first one I made was done REALLY quick and without much thinking, thus I fucked up.
Only thing you need to keep in mind is that before you animate you HAVE TO know how many pixels per frame your sprite will move. Then you are set.
"All" you need to do then is make the contacts first, space them out as far as they would in one full move. So say you have a 12 frame run and you go 5 pixels a frame you place the first frame twice on the sheet 60 pixels (12x5) apart and put the other contact in the middle and so on.
I found if I put the heads first with equal spacing and not on a "treadmill" but actually moving at what the sprite would move in game, and then do the body and legs, I got the best result. So yeh, robotacon and Ben are right. At the end once you did this spacing stuff you could even go over it and move shit around (as long as the feet on the ground stay at the same places) like drag the head or jut it forwards at the highpoint and stuff like that.