So, a preliminary issue is the term "head of state." I'll presume you meant this as a generalized term for any leader of a large group. Nation States are a phenomenom that are really only a few hundred years old, and the leader of a tribe or other group is not exactly the same thing as a head of state. The term doesn't translate exactly. If we're in a feudal-esque society with various leaders of city states or tribes, some of whom may be allied or owe allegiance to one another, are they all heads of state or is only the highest ranking one a head of state?

In any case, single combat between leaders is quite rare. Even in the Ancient era it was uncommon for important people to "lead the charge" so to speak, because everyone knew that was a good way to get killed.

On the other hand, in ancient times,just as today, tales were told of the bravery of ancient heroes who personally led charges against their enemies, and facing the enemy king in single combat. There are numerous examples in antiquity of legendary single combat between people that might nominally be heads of state, but many of them are almost certainly myth, such as Romulus defeating defeating Acro, or Menelaus and Paris or Achilles and Hector.

Livy has an account of the Horatii facing the Curatii (two sets of triplets) to decide a war between Rome and Alba Longa. Again, a high liklihood this is myth.

Some accounts may still be apocryphal or exxagerated, but ring slightly closer to true.

Plutarch recorded that the Roman Consul Marcus Claudius Marcellus fought the king of the Insubres in single combat at the Battle of Clastidium in 212 BC, and a different consul Marcus Licinius Crassus defeated Deldo, the king of the Bastarnae in single combat in 29 BC. There's little independent verification, so again, possibly dubius but moving somewhat more toward the possible end of the scale. (notably, these were also wars that involved Roman armies invading city states, so not necessarily huge scale battles).

The Rus had a tradition of single combat between Druzinas, not precisely heads of state, but worth mentioning. One of the most well known such duels was between Mstislav Vladimirovich, a prince of Tmutarakan in the Kievan Rus who fought Rededya, a prince of the Circassians, in 1022.

Flavius Odoacer deposed the last Western Roman Emperor Romulus Augustulus in 476 and crowned himself King of Italy. His rule would not remain unchallenged for long, however. Emperor Zeno of the Eastern Roman Empire appointed the Ostrogoth ruler Theoderic the Great as King of Italy in 489. In doing so, Zeno began a bloody war between the two claimants and alleviated two threats to his empire. Theodoric stormed the Italian peninsula and within a year nearly all of Italy was under control of the Ostrogoths. Odoacer took refuge in Ravenna and withstood attack for 3 years.

The siege soon drew to a stalemate where Odoacer and his men were unable to fight their way out but the Ostrogoths could not seize the city. A ceasefire was arranged where Odoacer and Theoderic would share control of the city. Odoacer was invited to a banquet to commemorate the end of the conflict, where he was supposedly killed by Theoderic while eating a meal.

Some sources say that he was struck down with a sword while others claim that Theoderic strangled Odoacer to death with his bare hands as he cried for God. As he kills Odoacer, Theoderic justified his betrayal by stating "This is what you did to my friends."

I don't know how you want to define 'head of state', but this is the best example that I know about. Odoacer wasn't technically the head of a nation or a state at the time of his death, only of half of the city of Ravenna.

I suppose the most famous example of "heads of state" (de facto, at least) actively engaging in personal combat is probably the clash between Takeda Shingen and Uesugi Kenshin at Kawanakajima. Kenshin was leading what I can really only describe as a hell-for-leather charge, spurred his horse right into Shingen's tent, and immediately immediately tried to kill him. Shingen was obviously unprepared for the attack and didn't have time to arm himself, so he had to make do with his tessen (a folding fan made with bits of iron that was sturdy enough to be used as an improvised weapon in places where samurai weren't permitted to carry traditional weapons like the katana). Kenshin was ultimately driven back and neither man was killed but the incident made the Takeda-Uesugi rivalry the stuff of legend.

And then there's Sun Ce. He was one of the early independent warlords during the Three Kingdoms era of China (c. 180-270 AD). He sought to expand into the region of Wu (which is vaguely defined but, generally speaking, refers to the easternmost bit of land immediately south of the Yangtze). In doing so he was forced to clash with numerous warlords. He defeated Liu Yao (who later died of illness) and then, after Yao's death, would go on to personally kill Xu Gong (it's not explicitly stated but Sun Ce was the "man who passes the sentence should swing the sword" type). In an unusual twist, Xu Gong would get a sort of postmortem revenge: his retainers ambushed and mortally wounded Sun Ce shortly thereafter. After Ce's death, the mantle passes to Sun Quan, who happens to outlive his chief his rivals by sheer virtue of being too damned stubborn to die. The more fanciful version of Ce's death, as told in Sanguo Yanyi, is that he kills a mystic and the mystic subsequent kills him as a ghost. Or something. It's weird.

The era's drama also includes a sort of subversion of the question posed. Lu Bu personally murders two warlords (first Ding Yuan, at Dong Zhuo's request, and then Dong Zhuo himself), sets up his own little power base, and is later executed by Cao Cao (who has him hanged as an insult; typically only women and disgraced men were subjected to that form of execution).

Mark Antony famously challenged Octavian to a duel. Octavian declined and eventually won the civil war anyway. Mark Antony supposedly challenged him to a duel, at any rate.

[Edit: how to grammar ?]

It's hard to tell what's myth, what's "king Bob and his personal household guard fought king Bill and his personal household guard" being rephrased as "king Bob personally fought king Bill" even if they never personally fought, and what's actually two heads of state genuinely fighting to the death.

That said, the first Neo-Persian (Sassanid) shah, Ardashir I, allegedly killed the last Parthian (Arsacid) shah, Artabanus V, in personal combat (using, ironically, a quintessentially Parthian tactic -- feigned flight followed by backwards shot while retreating).

What do you define as a head of state? Was a count or a duke a head of state?

During the Kalmar war in 1611, King Carl IX of Sweden did challenge king Christian IV of Denmark to a duel to settle the war between the two countries. Being in very poor health, such a duel would probably have been disastrous for king Carl, but the idea was ultimately rejected by king Christian.

Sources: Wadén, I, 1936, Skriftväxlingen mellan Carl IX och Christian IV efter Kalmar slotts fall 1611.

Although debatable, Massagetae Queen Tomyris killed Cyrus the Great and made a cup from his skull (this was offered by Heredotus among possible causes of death of Cyrus the Great).