Similarly stupid solution: use diplomacy to convince some giant melee monstrosity to go kill a Balor for you. Perhaps convince a few titans or solars? This should be doable at very low level... Venerable Unseelie Fey Magic Blooded Dragonwrought Kobold Marshal 1/Warlock 1/Binder 1/Bard 1 or something. With a basic +7 Cha on a starting Charisma 18, you could have a Charisma of 26 by level 4 without magic items. 7 ranks, + 16 Cha (including Motivate Charisma), +6 from your Warlock abilities, +2 from Sense Motive and Bluff and Knowledge Nobility and Royalty, +1 from wearing Glamorweave Clothing... that's +42 to Diplomacy checks (and you can take 10). Now just find a friendly Solar or ten. Make them fanatic. Have them run off and squish the Balor for you. Make sure they kill it in melee to fulfill the letter (not the spirit) of this challenge.
JaronK
If we're going the Diplomacy route, there are simpler ways than that, restrictions after a comma:
Spirit Friend [Ancestor], Phoenix Clan.
Soul of Green Walls, can only be taken at 1st level.
Spirit Friend makes all outsiders no worse than Indifferent to you. This already gives you the absurd advantage of the Balor not attacking you first, initiative solved. Then, if you really do want to persuade solars or whatever, you're not fighting an uphill battle.
The second lets you move the initial attitude one in either direction (so we'll go the positive direction, making Indifferent into Friendly).
There's a third feat I'm still trying to find again after not writing it down that basically does the same thing as Soul of Green Walls (with a little more limit, but none that actually matter), which would let you treat all Outsiders as initially Helpful to you.
That can easily be done at level 1 with Human or Strongheart Halfling or such and a Flaw. Where you go from there is up to you.