Measuring the step length during walking
It's actually a fairly difficult problem, depending on your constraints and requirements. Determining local positioning is prone to high levels of interference and accumulation of error. 

GPS will be way too inaccurate unless you setup a super expensive differential GPS system, which sounds like it would be too much for you.

You could use accelerometers/gyroscopes as you mentioned, but there is a reasonable amount of error depending on your funds and how much error you can tolerate.

I'm not exactly sure what the application of this project is, but a low cost solution could be to just mount some ultrasonic distance sensors to the shoes? Or you could use cameras and colored shoes to track the movement? Just some thoughts.

Personally I'd just tie a rope to the shoes and then I'd know how long every step would be :)