There is nothing saying a PADI instructor cannot work independent of a dive shop. Some agencies require the instructor to be affiliated with a dive shop but PADI is okay with an instructor working independently.
Finding an independent instructor is something entirely different. Like Kiwi303 points out, it is harder to find an independent instructor. Additionally, the costs are going to be higher. I work out of a dive shop as a DM and will continue to work for them when I become an instructor. The shop's liability insurance covers me. PADI requires proof of insurance in order for an instructor to be current. Buying insurance for myself will be a little more expensive then getting covered by a shop's insurance. Also, the shop will handle the paperwork. They will make sure students have all their forms filled out, they'll log the information with PADI, etc. For some instructors they like to dive and teach but hate the paperwork.
Additionally, a shop will give students discounts on things like tanks, air fills, pool time, etc. Training tends to be a break even or money losing part of the business around here. When you factor in rental gear. If I have 8 students I don't need just 8 sets of gear, I need gear for extra small, small, medium, large and extra large students. As an independent instructor, there is no way I can stock as much gear as a dive shop. I also don't have equipment sales to supplement my income. Even if I tried to sell equipment, I wouldn't have the same volumes as a dive shop. Students would tend to purchase all their gear from a dive shop or online.
Finally, as a dive shop instructor I would get use of the gear in the shop, free air fills, discounts on personal gear, informal training from the Course Director, I don't have to pay for advertising, etc.
Bottom line, there are independent instructors but if you are a PADI instructor you tend to work out of a dive shop because it is hard to compete with the PADI dive shops and you get additional perks from working out of the dive shop. Essentially, working out a dive shop seems like a win-win for the shop and the instructor.
That said, if you are looking for a more personalized, higher quality training. You might be able to find an instructor who will give you a better experience for more money. A dive shop will typically charge you $199 for your OW class and pool then you pay for the open water portion separately (some people go to the Caribbean, some finish up locally). If you look around you will find instructors with 5000+ dives, certifications galore, etc. Essentially, a dive shop might be people who are divers and want to supplement their habit. An independent instructor might be someone who takes teaching much more seriously and will give you a much better training experience.
Often the best independent instructors will require you to get enough people for a class (you and 3 to 5 friends). They will charge $1000 per student. They will expect you to buy your own gear and get your own air fills. REALLY well respected instructors (20+ years experience) will expect you to fly them in, arrange a pool and pay for lodging and food.
The way most independent instructors sell it, PADI is quick, easy and inexpensive to start. With a few hundred dollars you can get OW certified. But if you are going to the level I'm currently at, OW, Adventure Dives (Peak Performance Buoyancy, Drift Diver, etc.), AOW, Rescue Diver, Dive Master you will easily spend $1000+ for all your training. So do you pay $1000+ over many years or do you take a 5 day, intensive training for $1000 and be done with it.
As someone who works full time and dives as a hobby, I was attracted to the idea of getting trained on the weekend and devoting half days here and there over 10 tens. So I went PADI. Knowing what I know now, I would have gone independent.... however, 10 years ago I didn't know enough to find a good independent instructor, the people I would train with now weren't as qualified 10 years ago, etc, etc.
