How about a subscription service for something cheaper, then bring coupons along for various shoes with a discount?
Three years ago I would gladly have signed up for a mp3-player battery subscription, but of course now those come with built in battery to charge through USB.
Maybe a subscription for athletic tape? A lot of us go through one or two rolls a month, to avoid heel blisters and nipple bleading. The more rolls, the more shoe discount coupons.
Hey, maybe you could even ad space on the athletic tape and give it away for free and still come away with a profit? If the signing up process makes sure you're a runner (verifiable marathon time?) there should be no doubt to ad buyers that you're focusing in on the desired target group!