[slight hijack]The formal manner of adressing someone in Brazil is “você”. This word is derived from “vossa excelencia” (your excellence). Você is used for anyone who is not a member of the family (and almost the same age) or a very close friend (“tu” is used then). So basically, Brazilians go around calling everryone “Your Excellency”. Just another reason to love Brazil I guess. 
Similiarly, the Spanish “usted” comes from “vuestra merced” (your mercy).[/slight hijack]
I’ve also seen “Your/His Beatitude” for Metropolitans, and the Ecumenical Patriarch is often referred to as “His All-Holiness”. I’m sure there are others, and the terms will of course vary widely among languages. In liturgical services bishops are addressed as “Vladyko”, “Despota”, or “Sayyidna”, all of which are usually translated into English as “Master”. These are also used when addressing a bishop informally.
No historical cites, but from various cultural sources I’ve got the impression that “Your Excellency” was once the proper address for nonroyal heads-of-government. In the TV movie of Gore Vidal’s Lincoln, President Lincoln was several times referred to, in the third person, as “His Excellency” (though never address as “Your Excellency,” that I recall). I don’t know when the “Mister President” usage came in.
In Duck Soup, Rufus T. Firefly (Groucho Marx) is addressed as “Your Excellency” after he becomes premier (president?) of Fredonia.