Funny, I've not had that much trouble finding someone to change tires on wire wheels. Basically any shop that is equipped to handle alloy wheels (which is most of them today) should have a power changer that will also work well with wires. It needs to grab the wheel by the rim rather than the center, and ideally use a power arm that does not contact the wheel at all (only the tire). My local Wal-Mart has such machines, so does Costco.
Don't recall which one offhand, but I pulled off the highway into a Iowa city more or less at random (might have been Council Bluffs as I remember crossing a river), looking for tires on my way to VTR 2005 in Rockford IL. Pulled into the first tire shop I found (Firestone as I recall) and asked. They directed me to an independent shop just a few blocks away, where they not only knew how to handle wire wheels but had my size of tire in stock!