Old English/Titles and Nicknames< Old English
In Old English, title nouns usually came directly after the noun. For example: Ēadweard Cyning, Ælfrīc Munuc, Wēlund Ċild. You could also do the equivalent of the Modern English "John the King" or "Fred the Assassin", for example: se cyning Iohannes, se morðorwyrhta Hrōþgār.
Nickname adjectives like in "John the Short" and "Richard the Great" in Old English would come directly after the noun, minus the word for "the" (unlike in Modern English), would take the weak declension, and would agree in case, gender, and number with the noun they were modifying. For example: Carl Fǣtta - Charles the Fat, Offa Lytela - Offa the Litte; but in genetive: Carles Fǣttan (sweord) - Charles the Fat's (sword), Offan Lytelan (tæfl) - Offa the Little's (board game). Since regnal numbers (like the "II" in "Elizabeth II") don't seem to have been used in Old English, but since regnal numbers are ordinal in sense, and ordinals were grammatically adjectives in Old English, and adjectives were allowed to follow the noun (as has just been explained earlier in this paragraph), one could excuse something like "Elisabeþ II" as allowable in OE grammar.
Proper nouns, including personal nouns, could also be used with the definitive article and/or an adjective, like in Modern English "No - I don't mean that Sarah. I mean the other Sarah." For example, "se ōðer Iohannes" - "the other John (not that one)" or "John the Second". Such adjectives followed normal adjectival agreement rules.
Family names weren't really present in Anglo-Saxon culture, but one could think of them as "titles" and use the same constructions in grammar as for titles.