What options exist for creating a character focused on doing solely non-lethal damage? Are there ways to have increased damage output compared to a lethal-damage-dealing characters by accepting the restriction of being only able to do non-lethal damage as a trade-off? Can a character that only deals non-lethal damage be built as a "high damage" character, relatively speaking?
It's actually quite simple to do this. In the SRD, you'll see a rule that allows you to deal nonlethal damage with any weapon that normally deals lethal damage:
... which makes sense. You have to take much more care not to kill someone with a sword and just knock them out. But the option is there for you! And it makes for very cool character fluff, in my opinion.
Also, as @GMJoe kindly pointed out, there is a core enchantment in the 3.5 Dungeon Master's Guide (pg. 225) called Merciful for only a +1 bonus. You'll certainly want this (assuming you don't use one of the weapons which already deals nonlethal damage):
Other Source Books
The best sources for nonlethal damage in books outside of core come from the Book of Exalted Deeds:
Optimal Build (?)
So, really, it looks like your best bet would be to become a traditional, overpowered spellcaster, take the Nonlethal Substitution feat (which will allow you to use your spells to deal nonlethal damage), then use the various Vow feats to increase your other statistics. That looks like maximum leverage to me. I don't know of any other source books that would really contribute much to this effort.
As far as dealing more damage than a normal damage dealer, that is likely next to impossible without being very, very creative. For starters, there just aren't that many sources of nonlethal damage in the core rules. If you look in the Environment section, it might be possible for you to make some homebrew rules with your DM based on these (i.e., cold effects which numb instead of kill). If you want to stay strictly within the RAW, though, I think your best bet for having a highly functioning nonlethal character would be to have a spellcaster of some kind who only utilizes sleep spells, hold person spells, and the like. I didn't include this in the main answer because these effects don't technically deal damage, but it's an option which may appeal to you.
If you are looking to build a non-lethal melee build to keep up in comparative damage to lethal combat, I recommend the Justiciar Prestige Class. Found on pages 47-48 of the Complete Warrior source-book, The Justiciar is a full base attack progression class with good will saves. Appears to be intended for rogue or ranger classes (Entry reqs include the Track feat/class ability and 5 ranks of Gather Information, as well as Skill Focus- Gather Info) who want to play the period-appropriate "cop" (must be lawful alignment) or the "Worth more alive than dead" bounty hunter type. This class, for a 1-level dip, offers "Bring them Back Alive" and 1d6 "Nonlethal Strikes" which functions as (and stacks with) Sneak Attack, but only applies when using "Bring em back alive".
Pair this class with a class like rogue, ranger, or scout, the "Merciful" ability applied to any 2-handed weapon, a mid-range Intelligence score, and other standard melee build styles, and you should at least be able to keep pace damage-wise with a melee ranger.
As an added potential use, I used this PrC with a Razorclaw Shifter Rokugan Ninja/Scout build and the Vow of Poverty feat with the Vow of Nonviolence and Vow of Peace from BoED. The party Arcane Hierophant cast Greater Magic Weapon on my unarmed strike/claws and used permanency to make them stick. I followed up this class with levels of Kensai to improve my natural weapons. I ended up working as the "Royal Bounty Hunter", bringing Criminals back to the Capital for trial through 3 kingdoms...