I can't comment on it's frequency unfortunately because I haven't studied it in great depth but there is a very interesting account of one in Froissart's Chronicles (1322-1400) that is ample proof that it did exist.

In Froissart's account (you can read it in the Penguin edited edition if you want, I can get the page numbers for you if you're interested) he tells the story of a noblewoman who was raped by a local squire (worth noting here that in this time period a squire could easily be in his twenties, not necessarily a young boy) and reported this to her husband. It took some convincing but she got her husband to believe her that it had happened and he pursued legal action against the squire. Unfortunately it was basically the squire's word against the noblemans and no result could be reached. The Squire's lord was unwilling to punish him and after a few years of argument and accusation it was decided that the matter would be settled in a Trial by Combat. The nobleman and squire met in combat and the nobleman defeated and killed the squire (in the account it's clearly not an accidental killing either, he knocks the squire to the ground and stabs him with his dagger).

From Froissart's story you get the impression that this was very much an uncommon event. They settled on the Trial by Combat because nothing else could be agreed upon. I can't comment as to whether it was more common earlier in the Middle Ages. This is also based on my recollection from having read the account last year so there may be a few minor details wrong, I have the book on my shelf if you have any specific questions I could look it up.

I can't comment on the frequency but I can give the underlying justifying principle and partly answer the regard question, at least with respect to Carolingian Europe: trial by combat was a form of trial by ordeal. The victor in a trial by combat was in the right not because might makes right, but because God would clearly intercede in the combat to ensure the justified party emerged victorious. This is similar to other Carolingian/medieval trials by ordeal, such as the 'trial of the Cross,' where both claimants would stand with their arms outstretched for as long as possible, with the person able to hold the position longest obviously being aided and favored by God, and the trial of the cauldron, where both parties would have to retrieve an iron ring from the bottom of a cauldron full of boiling water—God would indicate the just claimant by healing their burns the quickest.

source: Thinking Medieval, Marcus Bull, The Carolingian World, Costambeys, Innes, and MacLean, the work of Geary

Trials by ordeal could take, according to Professor Robert Bartlett, two forms: unilateral or bilateral.

Unilateral involved one party undergoing a test by which the outcome of the case was decided. Trials could include throwing the accused into a pool or pit of cold water (sink you're innocent ; float you're guilty) along with more famous examples (see other answers). A priest would, for a trial by iron (heated metal held in the hand), sanctify the iron speaking thus:

Bless, O Lord, through the strength of your power, this metal, removing every demonic falsehood and dispelling the magic and trickery of unbelievers, so that it may be made clear to unbelievers, through your name.

Of course, this was asking God to perform a miracle on demand for rather temporal purposes. At the Fourth Lateran Council (1215) priests were prohibited from participation in these types of ordeal. After this death-knell trials by jury (usually of twelve men) became the norm (in England at least).

Bilateral involved either the parties or their champions to commit to battle. This was classified as a trial by ordeal (as others have said). It required one to put one's body in danger in defence of your claim and place the decision in God's hands. While there are extant examples of peasants fighting trials by battle most clergy and 'unfree' requested (and received) exemption from this form of trial. Nor did Lateran IV have any effect on these judicial battles.

As has been said these trials were supposedly settled by God but it was readily apparent in the late Middle Ages that God seemed to favour the strong, something Christine de Pizan noted in 1410. While clerics and humanists might deplore the judicial battle it remained incredibly popular. It was also intrinsically linked to the noble privilege of private warfare (which was essentially a judicial duel writ large). The private war and the judicial duel were both challenges to the authority and judicial hegemony of increasingly centralised and powerful monarchs. What finally killed them off was legislation and the prospect of facing judicial punishment even if you 'won' the duel.

A fascinating by-product of this tradition in England was the role of the 'Approver'. This was an unfree individual accused of a serious crime (eg. theft) who would become a gladitorial champion of the king against his fellow thieves! Amazing, eh? This continued after Lateran IV and I have absolutely no idea when it ended! If someone would like to fill me in on that particular detail I'd be delighted.

Primary:

• (ed. and trans.) F.R.P Akehurst, The Coutumes de Beauvaisis of Philippe de Beaumanoir, Philadelphia, 1992. | The Etablissements de Saint Louis: Thirteenth-Century Law Texts from Tours, Orleans, and Paris, Phildelphia, 1996.

• Christine de Pizan, The Book of Fayttes of Armes and of Chyvalre, trans. William Caxton, ed. and intro. A.T.P. Byles, Original Series No. 189, Oxford, 1937, p.261.

• (ed. and trans.) G.D.G. Hall, The Treatise on the Laws and Customs of the Realm of England Commonly Called Glanvill, Oxford, 1993.

• Henricus de Bracton, On the Laws and Customs of England, trans. S.E. Thorne, ed. G.E. Woodbine, 4 Vol., Cambridge, 1968.

Secondary:

• Robert Bartlett, England Under the Norman and the Angevin Kings, 1075-1225, Oxford, 2002, (bits from above): pp.180-184, 191.

• Maurice Keen, 'Treason Trials under the Law of Arms', Transactions of the Royal Historical Society, v.12 (1962), 85-103. | The Laws of War in the Middle Ages, Oxford, 1965.

(Edited to format references - bloody references!)

I can give you some context with one of my favorite medieval anecdotes, the tale of Jean de Carrouges! Jean was a French knight who served from the mid-late 1300s. He was heavily involved in military service and court politics, which led to the development of a few rivals. One of which is the bad guy of our story, Jacque le Gris. After a particularly bitter argument, and while both Carrouges and all his servants were away from home, Le Gris and a man-at-arms approached the home of Carrouges' wife, Marguerite. On the excuse of asking for the repayment of a loan, Le Gris forced his way into the household and then apparently declared his passion for Marguerite. When Marguerite spurned his advances, a bitter argument ensued which resulted in her violent rape at the hands of Le Gris.

Upon hearing of this, an enraged Carrouges immediately filed legal proceedings, but the trial was a sham. Not only was Le Gris a favorite of the judge, a local count, but Marguerite was female and her testimony mattered little in rape charges. Le Gris was acquitted and Carrouges appealed to the king himself for justice. He knew any sort of legal proceedings would be a sham so he demanded a trial by combat. According to Eric Jager in The Last Duel, such trials had once been common but by 1386 were incredibly rare. However, Carrouges so captured the imagination of the French court with his story that the trial was allowed, and the upcoming duel became the most anticipated spectacle in Paris.

There was sort of a festival atmosphere in the city as the duel approached. It was like a modern Superbowl, if Superbowls were seen once in a generation. Anybody who was anybody was sure to see it. I forgot to mention- the stakes were pretty high for all parties involved in the duel itself. Not only was this a fight to the death, but should Le Gris win, Marguerite would also be burned at the stake for perjury.

As for the duel itself, it was an incredibly close fight, but Jean de Carrouges won by breaking off Le Gris' visor and stabbing him in the neck. Le Gris was found guilty, Marguerite was avenged, and the last legal duel in French history was in the books.

The catholic church forbid all priests to be part of any form of trial by ordeal in the fourth Lateran council (1213-1215). Likewise emperor Frederick II. outlawed it in 1231 in the constitutiones regnae siciliae for his kingdom in Sicily/Puglia, with the distinct remark that it was too unsure whether God really showed himself. That means though that it must have existed, otherwise it would have been not necessary to outlaw it.