I suspect that pedometers are based on accelerometers because accelerometers are cheaper than GPS to use. in fact I think a lot of pedometers don't even try to measure distance. just acceleration jolts which equal steps. and then if they give you a distance measurement, it's by multiplying detected steps by a guessed or average step size.
GPS (if you are in an area where it works!) will do a very good measurement of distance. Even with a very cheap GPS receiver. All being basically OK, you should expect start and end positions to within 10m, and so for a 1km travel, you have 20m of uncertianty, which is 2% total distance uncertianty. This uncertianty goes down linearly with distance travelled (ie a 2km run will have 1% uncertianty, 4 km run will have 0.5% uncertianty, etc) the issues here will be with your realtime displays (GPS position jumps from satellite switching giving massive speed values, or immediate loss of signal giving a loss of all immediately displayable data)
I think that with a good accelerometer, starting from stopped you can continually integrate the signal to get speed, and continually integrate that result to get distance... I am just unsure what kind of accelerometer quality you get in any given phone? you may need to filter for noise or even garbage data.. And you also need to consider what accuracy it has. 20% accuracy in your sensor would make for a very bad distance tracker. So you might have to work with step counting and step size guesstimates.
perhaps a combination of both could work?
I'd be tempted to use the accelerometer data (either integrating or step counting depending on what will always work) to track speed and distance in short timeframe, then with much longer timeframe, generalised GPS data could be used to correct or scale that data from the accelerometer. Especially if you filtered/blocked GPS data based on uncertianty measurement at any given time.