Interesting idea.
The "Xerox copier" model for running shoes.
I submit the monthly tally for our office copy machines we rent. The machines have auto replenishment of toner, etc and we budget an exact amount at the beginning of each year, knowing that if a copy machine suddenly breaks we won't have to fork over $8,000 for a new one - Xerox has us up and running within 24-48 hours with not only a working machine, but the newest model available at the time.
You've got a couple of advantages/opportunities and a couple of serious drawbacks to the running shoe subscription model.
Remember, your customer will not subscribe unless there's something in it for him.
Advantages for the runner: Get him the latest model of nike, asics before they come out. Give him assurance that if his shoe has only 50 miles and the bottom suddenly peels off, he gets a new pair. Give him free shoe co. extras. If I am running in the nike vomero, I want the vomero 6 before anybody else gets theirs. I want access to exclusive online logs, iPhone apps etc. I want a nike personal fit assessment each year.
Drawbacks for the runner: He already knows he's spending $350+ a year on running shoes before the year even starts. He doesn't want to spend more than he would if he walked into his LRS and bought a great feeling new pair. He often needs shoes at different times, we all know YMMV, not when his personal odometer hits 500 miles.
Advantages for the service: Gets runner hooked. Keep this guy in nikes. Don't let him stray, feed him stickers, social networking crap, the works - free advertising also. If you get him to sign up for multi-month, or even multi-year service, it helps shoe co. and service big time. Secondary co. advertising on the online running log, etc catered to runner will be additional source of income.
Drawbacks for the service: Admin cost, not cheap if you hope to do it right - runners are picky. What happens if runners wants shoe he has, or newest model and it's no longer available or not in his hobbit-footed size? Can you keep the runner satisfied enough to tell his fellow runners. This will work if the "club" or service becomes something that feels exclusive and that won't be easy.