That's a tough list of requirements, but you've left out one factor. How many hours can you cycle at 13 mph? Ron Wallenfang, for instance, rode slowly from dawn to dusk (search for him on crazyguy), and rode a century or more per day. You may be able to do some of the commercial tours if you can manage that kind of daily distance. Most tourists seem to average 40-70 miles per day.
You might want to start your search with either the Cyclists' Yellow Pages, found off the main AC page, or the classifieds in a February or March issue of Adventure Cycling magazine.
If nothing else seems to work for you, you'll have two choices.
1. Carry your own gear and credit card tour. As long as you're hitting a motel and restaurant every day, your load will consist of clothes, water, and minimal supplies, tools, and parts.
2. Relax the absolute prohibition on camping, and look at a van-supported Adventure Cycling TransAm. One of the guys we met told me he almost never camped on that trip -- there was almost always a motel, B&B, or KOA cabin that he could rent. The van can carry a 3" thick Thermarest, which is pretty comfortable when you have to camp, as well as a sleeping bag and tent. Average age of the AC groups I've seen was probably late 50s / early 60s, and their daily mileages are reasonable.