Also considered another accelerometer and just approximating the time between steps and averaging it with the users average step length.
This is the only option (among your suggestions) that has a chance of working.
However, an ultrasonic ranger could ping in the forward direction, and if obstacles are encountered, both distance and velocity can be estimated. Range is up to 10 meters for the best of them.
Integrating IMU or accelerometer data is hopeless, as you can read about here.