What a great opportunity to work on the perfectionism.
I actually like the teacher's approach of not having a rigidly structured seating arrangement. It's teaching the children to be flexible and adaptable, and also providing them with more autonomy in selecting preferred seatmates.
In your shoes, I would practice making small choices within a reasonable amount of time at home. When you're out in public with more distractions and environmental stressors, I'd give DS control over decision-making. For instance, you go out for a coffee/hot chocolate at a cafe: where do you sit? what do you order? You browse at a bookstore: which aisles do you visit first? You attend a performance with no assigned seating or ride the metro/bus: where do you sit?
The key issue is to get around his paralysis by analysis and train him in quick, strategic decision making. Each interaction/decision is time-bound and of little importance, so the cost of "failure" is low. I think with some concerted practice, your DS is going to become much more comfortable with these decisions, and quite quickly.
