This could go quite complex...
As you have observed, you have no idea what the surface of the terrain is at any given moment, plus steps, incline etc.
Your last thought seems to be heading along the right path (*no pun), but you can do all that with a single 3D accelerometer. The difficulty is still the accuracy of the 'step size'. It could be a doddery old fellow, that steps 12 inches per step, vs a younger user at 18-20 inches.
I'm sure there must be a way to bring all the data together for something... perhaps that nicluides the time taken between each pass of the walker's leg? Tied with angular velocity, etc.