Yoyoils,
In the industry, propionic acid is prepared by reacting ethylene with CO and H2 catalyzed by Co, Rh or Ru catalysts, in a process called "hydroformylation". This reaction yields propionaldehyde, which is then oxidized with air as you suggested. This is how large scale manufacturer do.
As for a "on paper" answer, you should consider oxidizing 1-propene as suggested bellow. However, you have to realize that 1- and 2-bromopropane will both yield 1-propene after an E2 reaction (use t-BuOK instead of an hydroxide source to avoid Sn2 reaction taking precedence). You can then wrap this synthesis up with a little bit of your favorite oxidizing agent.