I'd make him a melee monster
For a solid CR25
Elite Array (+1 CR)
Wealth as a Lvl 25 NPC (350K)
Replace at-will insanity with at-will plane shift
Replace at-will telekinesis with (Su) double strength protection against good circle
Replace Quicken Spell-like ability with Improved Critical (Falchion)
Replace Two-Weapon Fighting with Weapon Focus (Falchion)
Replace Weapon Focus (longsword) with Improved Bull Rush
Replace Improved Two-Weapon Fighting with Improved Sunder
Feat (21HD) = Combat Brute
Feat (24HD) = Power Critical
Bonus Fighter Feats: Shock Trooper, Leap Attack, Weapon Specialization (falchion)
Cha Increase +1 (24HD)
Drop the whip and use a falchion. Use leap attack + heedless charge from shock trooper: dump the AC into Power Attack for insane amounts of damage and a massive crit range. Use sundering cleave from Combat Brute with adamantium falchion to obliterate opponent's magic arsenal and kill them. Good Cha also gives oomph to SLAs.
Graz'zt should feel at least a little wary of him. Looking over his shoulder, so to speak. It pays to be suspicious of one's generals.
"Memphis"
Balor Fighter 4
Large Outsider (Chaotic, Extraplanar, Evil)
Hit Dice: 20d8+240 plus 4d10+48 (400 hp)
Initiative: +10
Speed: 40 ft. (8 squares), fly 90 ft. (good)
Armor Class: 41 (-1 size, +7 armor, +6 Dex, +19 natural), touch 15, flat-footed 35
Base Attack/Grapple: +24/+43
Attack: +2 adamantine speed thundering falchion +40 melee (2d6+26/15-20)
Full Attack: +2 adamantine speed thundering falchion +40/+40/+35/+30/+25 melee (2d6+26/15-20); or 2 slams +37 melee (1d10+15)
Space/Reach: 10 ft./10 ft.
Special Attacks: Death throes, spell-like abilities, summon demon
Special Qualities: Damage reduction 15/cold iron and good, darkvision 60 ft., flaming body, immunity to electricity, fire, and poison, protective aura, resistance to acid 10 and cold 10, spell resistance 28, telepathy 100 ft., true seeing
Saves: Fort +26, Ref +20, Will +21
Abilities: Str 40, Dex 22, Con 34, Int 26, Wis 24, Cha 30
Skills: Bluff +37, Concentration +39, Diplomacy +45, Intimidate +41, Jump +46, Knowledge (arcana) +35, Knowledge (the planes) +35, Knowledge (religion) +35, Knowledge (history) +35, Listen +42, Search +35, Sense Motive +34, Spellcraft +39 (+43 scrolls), Survival +10 (+14 tracking), Spot +42, Use Magic Device +37 (+41 scrolls)
Feats: Cleave, Combat Brute, Improved Initiative, Improved Bull Rush, Improved Critical (falchion), Improved Sunder, Leap Attack, Power Attack, Power Critical, Shock Trooper, Weapon Focus (falchion), Weapon Specialization (falchion)
Challenge Rating: 25
Memphis’s natural weapons, as well as any weapons it wields, are treated as chaotic-aligned and evil-aligned for the purpose of overcoming damage reduction.
Death Throes (Ex)
When killed, Memphis explodes in a blinding flash of light that deals 100 points of damage to anything within 100 feet (Reflex DC 34 half). This explosion automatically destroys any weapons the balor is holding. The save DC is Constitution-based.
Protective Aura (Su)
Against attacks made or effects created by good creatures, this ability provides a +4 deflection bonus to AC and a +4 resistance bonus on saving throws to anyone within 20 feet of Memphis. Otherwise, it functions as a magic circle against evil effect and a lesser globe of invulnerability, both with a radius of 20 feet (caster level equals the demon's HD). This aura can be dispelled, but the demon can create it again as a free action on its next turn. (The defensive benefits from the circle are not included in Memphis’s statistics block.)
Spell-Like Abilities
At will— blasphemy (DC 27), dominate monster (DC 29), greater dispel magic, greater teleport (self plus 50 pounds of objects only), plane shift (self plus 50 pounds of objects only), power word stun, unholy aura (DC 28); 1/day—fire storm (DC 29), implosion (DC 29). Caster level 20th. The save DCs are Charisma-based.
Summon Demon (Sp)
You've tweaked this.
Flaming Body (Su)
The body of a balor is wreathed in flame. Anyone grappling a balor takes 6d6 points of fire damage each round.
True Seeing (Su)
Balors have a continuous true seeing ability, as the spell (caster level 20th).
Skills
Balors have a +8 racial bonus on Listen and Spot checks.
Equipment:
Large +2 adamantine thundering speed falchion
Large +3 heavy fortification mithral chain shirt
Other stuff to taste