First of all, feet are pretty darned complicated. Just because one thing worked for one person (or even a whole mess of people) doesn't mean it will work for you. Before you try things you really and truly need to figure out what your foot is doing and why it's doing it. Don't take anyone's specific advice based on your general description. And frankly, that works for every medical question ever posted online.
Custom orthotics are great for a tiny handful of people, another tiny handful of people can get by with store bought orthotics, then another group does better with barefoot, then another group needs a lot of cushion...then some just need to stretch and exercise. Well we all probably need that last bit.
I'm going to get into a bit of hot water here I bet, but I have been terribly disappointed with the practice of podiatry. GENERALLY speaking, and referring to most of the ones i work with, they inject everything despite a rather substantial and established body of evidence that steroid injections are bad bad bad bad for just about every bit of soft tissue. They give everyone orthotics (really? No one has a foot that can contact the ground adequately?) and they seem to believe all the great advances of the 1980s are still the best ways to address tendon and joint problems of the foot and ankle.
So what do you do?
Basically someone needs to look at your foot: how it moves, where is it stiff, where is it weak, etc. Someone needs to watch you walk, look at the whole leg: how does your hip move? Your knee? Do your arches fall or are they stiff and high? Do you have no arches to begin with?
The cheapest and easiest way to start, especially if you aren't too far down the road to injury, is to be fitted for shoes at a good running store. The best ones watch you walk, maybe even videotape you, then tell you what kind of shoe to get.
All due respect to Roger, sometimes the inserts from the drug store are actually a good thing. I frequently get patients with atrophied fat pads of the heel and the best thing they can do is put a gel insert into the heel. And sometimes, for difficult metatarsal pain, met pads are actually a great way to temporarily relieve pressure while the underlying tissue heals.
As a physical therapist I am certainly biased towards PT as an effective intervention...but with a HUGE caveat. There is some seriously bad PT out there, and it might be just as hard to find a good PT as it is to find a good podiatrist.
So the bottom line is that someone needs to look at the biomechanics of YOUR foot and ankle. Don't let anyone inject you with anything, don't waste money on electrical stimulation or ultrasound or iontophoresis or any of that bogus crap.
That was a whole lot of negativity...sorry. Feel free to PM me if you want some specific suggestions...I'd need to ask you a lot of questions first tho.