The usual ways to avoid an AoO:
- Tumble
- Spring Attack
- swarming him (so he doesn't have enough AoO's to get everyone)
- use reach weapons
- use ranged weapons
- use 5' steps + total defense
- catch the character flat-footed
- teleport next to the character
Of course, the character probably has taken Combat Reflexes, and thus can make a few AoO's a round, and while flat-footed.
I don't know about other special feats that might let someone avoid potential AoO's.
AR
These are good ideas. Tower shields that grant cover don't incur AoO's. A good choice of a ranged fighter with the bow feats can make short work of a melee only opponent.
The other thing is that you can have your player play his uber character and allow him to play his strengths through some combats and then mix it up with other factors. For example, since the minotaur has reach and is going around killing everything, the defenders are going to get wise and set up barriers for cover, they are going to switch to ranged weapons to take down the killing machine, and so on. It's the same if your group of players has an over-effective spellcaster. The enemies, if given time, will adapt.
Just recently, I ran an encounter where the PC's were fighting the high-level cleric cultist. The sorcerer evoker opened up the combat with her hellfire ability. Bad mistake, because that immediately made her the target for the cleric's destruction in which she failed her save and was obliterated.
In another combat, the ranger with her awesome bow shots was going around hitting a rogue group of cavaliers. They were not afraid of the paladin who did uber damage because they were able to outmanuever him and the sorcerer at the time wasn't using blasty spells, so the lead cavalier issued his challenges and charged the ranger and skewered her with his deadly feat combos for mounted combat. She survived the combat, but had to flee the battle as she couldn't take another hit.
Also, if you have monsters that are large size or bigger, they have reach too.
