Edit: This is not what the OP asked but I'm leaving it here as an (example?) of how you can get access to different travel methods in Minecraft.
During early game, kill pigs and cows, when smelted their meat is the most efficient feeding in the game. This supply will allow you to mostly sprint when you want to.
Towards the middle game you will want to get a saddle and tame a horse with wheat. this will give you the prefect, speedy method of travel that you are looking for and it will hardly cost you anything in terms of food for the horse (though you will need wheat for keeping its health up).
From then on you should have an easy method of medium / long distance travel and you should have farms set up to provide you with food for short distance sprinting and health regen.
Hope this helps, if you need me to clarify then leave a comment and I'll try to get back to you :) ~Jay