I just asked this question a few days ago as to whether or not duels actually happened before a battle.

http://www.reddit.com/r/AskHistorians/comments/2nybkz/did_duels_actually_take_place_before_a_battle/

Not really to many answers but the book that I read is called:

Khalid Bin Al-waleed: Sword of Allah: A Biographical Study of One of the Greatest Military Generals in History A.I. Akram,A.B.

Some of the sources particularly for the battle I will describe are from Ibn Hisham and Ibn Sad who both lived about 150-200 years after the event but their source can be considered reliable (I guess just as reliable as any source written or copied after the event) but it still should be taken with a grain of salt because they are very descriptive, so much so they even name who killed who in the first couple of battles, specifically for Khalid.

Anyway at the Battle of the Ditch which is when the Quraish were besieging Medina, a very similar story of David and Goliath takes place. A giant named Amr bin Abdu Wud challenges the Muslims to fight him in a duel. No one agreed until Muhammad allowed Ali to fight the giant. The slow giant could not hit Ali and Ali killed him by stabbing him in the throat with Zulfiqar. After that fight the Quraish and their allies stopped fighting for that day. After Khalid's failed attempted the next day the Quraish and their allies left and the Muslims were victorious in defending Medina.

I dont think anyone would question that Khalid bin Al-Waleed and Ali existed but as to whether this actually happened is questionable. It could be a fabricated story to glorify Ali, specifically for Shiite Muslims even though both authors were Sunni.

In all the later battles that Khalid commands/fights in (after he converts to Islam) against Romans and Persians there is always a description of duels between champions before the battle. What I mean by duels is one on one fighting before the battle as both armies watch, not just before the battle though it also applies after both armies regrouped. In all those battles that Khalid commands/fights in, the duels do not stop the battle from beginning or restarting like how the Battle of the Ditch incident did.

As for any Roman, Greek, Persian etc duel champions, I have never seen any historical sources but I would like to know also.