It has long been assumed, particularly in the SCA, that names of the form ______ al-Dīn, ______ al-Dawla, etc. (hereafter "titular names") are restricted to only those of the highest levels in government and religion; and, further, that such names are only granted by caliphs, sultans, etc. However, this isn't true thoughout Islamdom, throughout the Middle Ages and Rennaisance.
One note before I begin: according to Arabic grammarians, such names are a type of laqab, differing from other laqabs by coming at the beginning of the name instead of at the end. However, to the amateur onomast, this is unnecessarily confusing; by placement and by the use of multiple words, titular names differ strongly from laqabs as such. I will, therefore, use "titular name(s)" except when quoting sources that call them "laqab(s)" or "laḳab(s)".
To begin with, there's no sign of titular names any earlier than 909 CE, with the first ʻIzz al-Dawla [1], and the first titular name using ______ al-Dīn doesn't show up until 998 CE [2]. Thus, more than two-and-a-half centuries passed between the time of the Prophet Muḥammad and the beginnings of the use of titular names.
Futhermore, in some parts of Islamdom, titular names passed out of the realm of the high-and-mighty, and were given to even minor functionaries. Ibn Baṭṭūṭa, circa 1325 CE, travelled across the North African coast, and reported (usually very briefly) on every two-bit town he passed through [3]. Every town had a "governor" and a qaḍī, and many had a person famed for religious reasons. The vast majority of these people had titular names. Clearly the headman of a village is not on the same level as a general, a wazīr, or the head of a major madrasa.
But the widespread nature of titulars is really pointed out when Ibn Baṭṭūṭa says [3]:
As each scholar or notable arrives [the naqīb of the turban-wearers] meets him and ushers him in with the words "In the name of God! our Master So-and-so al-Dīn"
or when he partly quotes someone:
...saying, "in the name of God, so-and-so al-Dīn" such as Kamāl, Jamāl, Shams, Badr and the rest...
Then in volume 2, he explains a servant he just referred to [4]:
The office of this remembrancer is...When [in the amīr's audience hall] a respected jurist or man of consequence comes in [to say] "Bismillāh, our lord so-and-so al-Dīn, bismillāh," whereupon those who are present prepare for the entry of the visitor,...
Even more pointed are the remarks of Ibn Jubayr [5], circa 1182 CE:
THE MONTH OF RABIʻ AL-AWWAL (580 [AH])
The Lord of this city (Dunaysar) is Qutb al-Din,...These countries are subject to various rulers, after the fashion of the kings of the Arab nations in Spain. All these rulers embellish themselves with titles connected with religion [Din], and you will hear only awesome by-names and appellations that for the wise are without profit. In this, the subjects and their kings are the same, and the rich share the habit with the poor. Not one of them is known by a cognomen that fits him, or is described by an epithet of which he is worthy. Not one save Salah al-Din [Saladin],...Here the name is in harmony with the subject, and the words fit the meaning. All other titles are but a gust of air, and testimonials made void. The taking on of religious titles: what troubles they involve!
{emphasis added}
Or later:
THE MONTH OF JUMADA AL-ULA (580 [AH])
...while the managers of the [funeral rites] raise their voices to announce the venerated and leading men of the city {Damascus} as they arrive at the ceremony, vesting them with imposing appellations of distinction, which they confer on all alike, and all referring to din [religion]. You will hear whatever you wish: Sadr al-Din, Shams al-Din, Badr al-Din, Najm al-Din, Zayn al-Din, Baha 'l-Din, Jamal al-Din, Majd al-Din, Fakhr al-Din, Sharaf al-Din, Mu‘in al-Din, Muhyi 'l-Din, Zaki 'l-Din, Najib al-Din, without a limit to similar false titles. Particularly in the case of jurisprudents you may have such designations as Sayyid al-‘Ulama, Jamal al-‘Immah, Hujjat al-Islam, Fakhr al-Shari‘ah, Sharaf al-Millah, Mufti 'l-Fariqayn and such-like pretentious epithets without end.
Clearly, titular names were widespread, and not much of a distinction at all.
A bit earlier, circa 1045 CE, in Sicily, after a Byzantine invasion failed:
The Muslims of Sicily united around a brother of al-Akḥal, al-Ḥasan b. Abi'l-Futūḥ, who took --- or was awarded by the Fatimid caliph --- the title Ṣamṣām al-Dawla, 'Sword of the State'. [6]
Thus it is shown that taking a titular name was well known by the mid-11th century.
Across the years, many other leaders took a titular name; too many to list. However, I will adduce one more example:
Barbarossa...original name Khiḍr...Hatred of the Spanish and Portuguese...encouraged Khiḍr and his brother 'Arūj to intensify their piracy..ʻArūj was killed...in 1518, Khiḍr, who had been his brother's lieutenant, then assumed the title Khayr al-Dīn. Fearing he would lose his possessions to the Spanish, he offered homage to the Ottoman sultan and in return was granted the title beylerbey... [7]
Thus, we see someone who assumed a titular name and afterwards was given a title per se by a sultan, thereby acknowledging the self-given titular name.
One thing must be noted in all of the above: though self-granted titular names have now been proven, these are all important people---kings, generals, scholars, qaḍis, admirals, etc. What of common people? Other than ibn Jubayr's note regarding poor people (quoted above), there is, so far, no indication that ordinary folk took their own titular names. Thus, we must return to the Encyclopaedia of Islam's article on ʻIzz al-Dīn [2]:
In the course of the 7th/13th century, however, the laḳab lost its status as an honour granted by the caliph or a local prince, and became simply a name which a man assumed himself or which was attributed to deserving people by contemporaries without any official procedure....By the end of the Saldjūk period, at the latest after the arrival of the Mongols, who were first converted to Islam with Ghāzān Khān (694/1295-703/1304), the laḳab must have lost the character of an officially bestowed honour....from the beginning of the 10th/16th century at the latest, dīn titles were no longer considered as alḳab in the true sense, being reduced to mere proper names. [NB: alḳab is the plural of laḳab.]
Then, too, there's the remarks of Annemarie Schimmel [8]:
After 1200, compounds with ad-dīn became part and parcel of the name, the person's qualities or rank notwithstanding...It is significant that already in the early eleventh century al-Bīrūnī mentions...the nonsensical use of pompous epithets which had become "clumsy to the highest degree, so that he who mentions them gets tired before he has hardly begun, he who writes them loses his time in writing, and he who addresses (people) with them runs the risk of missing the time for prayer"...the use of names with ad-dīn very soon became a custom in the Middle East as well, as a look at biographical dictionaries shows, and when Ibn Maymūn (d. 917/1511) reached Egypt from his Moroccan homeland he complained that the people had exchanged good Sunni names like Muḥammad or ʻUmar for Shams ad-dīn or Zayn ad-dīn respectively, thus introducing a bidʻa, a heretical innovation...
So we see that titular names spread to the ordinary folk and, by the mid-13th century or earlier, were no longer awarded by caliphs, etc., nor taken only by the powerful, but had become the usage of all people from all levels of society. This leaves a considerable length of time before the end of the Rennaisance (or the SCA's period) when titular names were used by all who wished.
In other words, titular names, far from always being something special handed out by caliphs and sultans to the powerful, the holy, and the rich, were (in many places and times) something that just about anybody would give himself [9] and which would be accepted and used by those around him.
[1] The Encyclopaedia of Islam, 2nd edition, volume 4, s.n. ʻIzz al-Dawla. Note that most of the Encyclopaedia of Islam's discussion of titular names is found in this entry.
[2] op. cit. s.n. ʻIzz al-Dīn.
[3] The Travels of Ibn Baṭūṭṭa, volume 1, as translated by H. A. R. Gibb
[4] The Travels of Ibn Baṭūṭṭa, volume 2, as translated by H. A. R. Gibb
[5] The Travels of Ibn Jubayr, as translated by J. C. Broadhurst
[6] Arabic Sources for Sicily, by Jeremy Johns
[7] The New Encyclopaedia Britannica, 15th edition, volume 1, s.n. Barbarossa
[8] Islamic Names by Annemarie Schimmel, chapter V, "Lions, Moons, and Roses"
[9] There are a very few examples of titular names used by women, and the only ones I've found are late, and in Turkish mileus. Further, the ones I've found use Sitt or Khatūn, which are titles in their own right. This does not mean, however, that titular names cannot be used by women, nor even that using such a name is "bad re-creation". Any woman re-enactor who wishes to use a titular name should go right ahead.