There are several instances of this mentioned in history books but as to their veracity one can never be certain. First of course was the 3 vs 3 battle of the Horatia and Curiatia brothers for Rome and Alba Longa (even though this wasnt single combat I think it meets the jest of what the OP wants and this is the most probable story of the lot) The second case was between Titus Manlius (yeah I know best name ever right!) who fought a Gaul leader on a bridge in single combat, after he won the Gauls retreated.
Tacitus mentions that Germans would have their "hero" fight a captive of the army they were about to face, if their hero won then the battle would commence, if otherwise they would decline battle or seriously rethink their strategy. No names mentioned though.
sources: Oakley, S. P. “Single Combat in the Roman Republic” The Classical Quarterly, New Series 35.2 (1985): 392-410. & Solodow, Joseph B. “Livy and the Story of Horatius, 1.24-26” Transactions of the American Philological Association 109 (1979-): 251-268.
The historian Gregory of Tours mentions that the Germanic tribes in Spain (Vandals mainly) would often settle disputes between kingdoms with single combat between heros, again though he does not cite any specific examples.
There is a legend that Canute and Edmund Ironsides battled in single combat to a draw and upon the draw they decided to rule their kingdoms together, though I think this one is highly unlikely.
source: Ashdown, M. “The Single Combat in Certain Cycles of English and Scandinavian Tradition and Romance” The Modern Language Review 117.2 (Apr., 1922): 113-130.
In more recent times there is a story about single combat between indian chiefs, in fact the city in Wyoming called Crowheart is named after one. The story told is, to quote wikipedia ... link
"According to legend, following a five-day battle for rights to the
hunting grounds in the Wind River Range, Chief Washakie of the
Shoshone and Chief Big Robber of the Crow agreed to a duel, with the
winner gaining the rights to the Wind River hunting grounds. Chief
Washakie eventually prevailed, but he was so impressed with the
courage of his opponent, that rather than scalp him, he instead cut
out his heart and placed it on the end of his lance."