For my run clinic, I'm developing a rather basic recipe for getting non-runners running:
1. You don't start running by running. You start running by performing stationary exercises to build leg and core strength, then dynamic exercises to develop/improve the muscle firing patterns needed for running. Simply being able to walk is not enough.
2. The #1 thing that matters in running shoes is how the shoes feel when you run in them! Unless you are an experienced runner, buying shoes without running at least 1/4 mile in them is foolish. It's like buying a car without a test drive at freeway speeds. Of course, this implicitly requires that you know how to run before buying running shoes! Which by inference means that we should learn to run without running shoes! Huh? What?
3. Learn to run in a manner where the shoe doesn't matter. Let's get some old-school sneakers, like Vans or Converse, or perhaps some flat deck shoes, with a comfy fit that doesn't bind the toes. Next, develop the skills needed to run slowly with a high cadence and short stride by starting with stationary running drills. When the legs are ready, start running slowly on a soft surface, such as a football field or a padded track. Slowly build distance until you can run (not jog) a mile non-stop (however long it takes).
4. Then go shopping for running shoes. With fresh legs. Try out lots of shoes, like 20 pair or so, over several shopping trips. Develop a feel for what shoe features matter, which ones don't matter, and which ones don't work for you at all. Take notes, and keep them with you. Buy the cheapest shoe that feels good when running and has no significant faults.
5. Now we're ready to gradually add both distance and speed, followed by some rolling hills. Within a month or two, your shoe needs will change: Repeat the prior step.