The 14th century in the greater Middle East is...weird. In the 14th century in most of Islamdom you're actually dealing with a non-Arabic military aristocracy (that's not the weird part, that actually became the norm really early, I'll get to the weirdness). So in Egypt and the Levant you have the (Turkish-speaking) Mamelukes, in greater Persia you have the Mongolic Ilkhans and then the Timurids, and in Anatolia after the break up of the Seljuks of Rum you have these march states known as the Anatolian beyliks which is just this stew of Turkic jihad states rising and falling and out of which eventually will rise the Ottomans towards the end of the century.

Perhaps needless to say then the hierarchy of titles was anything but regular. Depending on where you are one's title in the military aristocracy might plausibly be in one of several languages. The 14th century is where we're starting to get to the point where Turkish titles are predominant (even on the Mongol armies, once they get this far west, you're dealing with a lot of Turkic-speaking tribes making up those armies.)

What was the highest title that an Arab ruler could claim for themselves, short of Caliph?

This is a really interesting question and it's where we start to get into the weirdness I mentioned earlier.

Remember that the Caliphate basically ends in 1258 with the Mongol sack of Baghdad and the death of the last proper Abbasid caliph. The Mamelukes ostensibly have "an Abbasid caliph" in Cairo, whom they use for legitimation purposes for about five minutes and then proceed to completely forget that these people exist. The Caliphate, as we understand as a unique title representing religious leadership of all of Sunni Islam, is de facto vacant from 1258. Already in the time of al-Ghazali in the 12th century though this was a shell of an authority, so H.A.R. Gibb quotes Ghazali as saying:

"We consider that the function of the caliphate is contractually assumed by that person of the Abbasid house who is charged with it, and that the function of government in the various lands is carried out by means of sultans, who owe allegiance to the caliphate. Government in these days is a consequence solely of military power, and whosoever he may be to whom the possessor of military power gives his allegiance, that person is the caliph."

Gibb explains the 14th century result better than I can:

From this passage it is clear that the caliphate, as represented by the Abbasid family, was no longer regarded as conferring authority, but merely as legitimating rights acquired by force, provided that the holder of military power, by giving allegiance to the caliph, recognized the supremacy of the Sharia. When the caliphate of Baghdad was extinguished by the Mongols in 1258, it remained only to take the last step and to declare that rights acquired by force were legitimate in themselves, and that military power constituted a valid Imaraa. The nominal "shadow-caliphate" set up at Cairo made no difference, since it receives no recognition in the works of any authoritative jurist. It was indeed a chief qadi of Cairo under the Mamluks who gave lhe final consecration to secular absolutism. The relevant passage of Ibn Jamaa's Tahrir al-Ahkam is too well known to need quotation again here,5 but one sentence is particularly significant: "When the Imama is thus contractually assumed by one person by means of force and military supremacy, and thereafter there arises another who overcomes the first by his might and his armies, then the first is deposed and the second becomes Imam, for the reasons of the well-being and unity of the Muslims."

The result is that quite a lot of people actually did claim for themselves the title of Caliph in the 14th century, though none of them were Arab as far as I'm aware. From the Encyclopaedia of Islam:

Various princes of this period refused, however, to recognise the Abbasid caliphs of Cairo. This happened notably in the case of the Il-Khanid Ghazan Khan, who occupied Damascus in 698/1299 and had himself named in the khutba "the august sultan, sultan of Islam and the Muslims". As for the Timurid Shah Rukh, he considered himself sovereign by divine right and it was his ambition to be recognized as khalifa by the other princes which was refused by the Mamluk sultan Barsbay and the Ottoman sultan Murad II.

Moreover, it seems that from the end of the 7th/ 13th century onwards, certain princes introduced the word khalifa into their titles, without however appropriating the title amir al-muminin; this was done by the Saldjuk sultans of Rum, protected by the Mongols, and also by the sultans of Dihli. The Turkmen Uzun Hasan (857-82/1453-78) wrote ca. 875/1471 to the Ottoman sultan concerning his new capital Shiraz, calling it the "throne of the caliphate". At the be- ginning of the 10th/16th century the prince of Transoxania, Muhammad ShaybanI, put on his coinage the title khalifat al-Rahman. While it is admitted that these titles did not always correspond to a precise aspiration, it appears that from the time of the Mongol invasions onwards, the title of khalifa was no longer reserved for the Abbasid amir of the Believers and that a number of rulers did not hesitate to take it up, as though it were a normal title of Muslim sovereigns.

This title appeared notably in letters of congratulation addressed by allies to Ottoman sultans after certain of their successes. Thus Murad I at the end of the 8th/14th century saw fit to call himself "chosen khalifa of the Creator", and "shadow of God on the earth". A little later, the sultan Bayazld did not hesitate to apply to himself verse VI, 165 of the Kuran: "we have made of you a representative (khalifa) on the earth." In the same way, Mehemmed I after the restoration of the Ottoman empire at the start of the 9th/i5th century, spoke of his "caliphate", a term which the other Ottoman sovereigns did not hesitate to use on certain occasions in dealings with their allies. At all events, and in spite of the fact that Mehemmed II the Conqueror did not take to him- self the title of khalifa, official correspondence addressed to the Ottomans by their neighbours did not cease to consider them repositories of the caliphate and Selim himself, after 1512, was called by his brother "shadow of God on earth".

Anyways, as I said it's quite a weird period of history and one which unfortunately I don't know all that much about.

I'm especially curious about Malik - how common was this in the period before the Ottomans?

Again, I turn to the Encyclopaedia of Islam. Ironically it was the number of rulers using "malik" as subset of their titles that seems to have caused its decline (in addition to the pettiness of mere "kingship" which is discussed earlier in the article):

The increasing number of potentates identifying themselves as malik gradually rendered the name less majestic, for it came to imply limited sway over one realm among many, and subjection to a supreme suzerain. Its devaluation, once again, was reflected in the fact that many a ruler assumed, in addition to malik, other and more pretentious designations. Several Buyid heads of state (e.g. Djalal al-Dawla, BahaD al-Dawla) and Ayyubid ones (e.g. al-cAdil) adopted the epithet malik al-muluk, modelled on the Persian shdhdnshdh; while others called themselves sultan [q. v. ], a title superior to malik as it conveyed a sense of independent sovereignty. The Mamluks, in a similar manner, combined these last two names, iden- tifying themselves as al-malik al-sultdn, while calling high-ranking governors in the Egyptian and Syrian provinces malik al-umard^ i.e. chief amir. In one in- stance in the Mamluk state the term was employed in the feminine, as the regnal designation of Shadjar al- Durr [q v,] (d. 655/1257), who entitled herself malikat al-muslimm. Another occurrence of the name in the feminine was in India, where malik was not other- wise in use; the queen Radiyya [q.v.] of Dihlf (634-7/1236-40), the only female ruler in Muslim In- dia, adopted it in lieu of the title sultan carried by the male members of the dynasty.

The depreciation of the title was apparently the main reason for its disappearance in later times. The Ottoman Sultans did not commonly use it. By the time when they were in power, the name retained but little of its former glory.

I'll continue in a part II as I'll soon hit the character count.