Since the gods were thought to be creators of the world, it was quite difficult for ancient people to think the gods were unrelated to the power in some manner. Any leader (not only king but also a general) had to convince their people and soldiers that the gods were at least loyal to their side to maintain good morale. Also in the ancient states often the only two branches of power were the religious one and executive one, thus the inauguration was performed by the supreme priest as the second-important figure in the state.
That said, the Roman emperors did not claim the divine mandate. Their power was in theory delegated by the people and senate of Rome. You of course heard that they were proclaimed "divine" sometimes, but usually post-mortem, and this was a honor conferred by the decision of the senate (and did not imply the dead were gods but just god-like). There were also temples of the "Emperor's genius", genius being a minor god, personal protector of the emperor (all people were thought to possess a genius as well). That is the people just honored the personal protector of the emperor so that his life to be safe.
Some emperors just like other noble Romans traced their ancestry to gods, but this was never used to justify their special rights to the power.
But I am not sure that this case falls under your request because the empire was officially a republic until the reign of Heraclius who after he defeated the Sassanid Empire adopted the title "King of Kings" (Basileos Basileon) which was previously held by Khosrov II, the defeated Sassanid king. It should be noted meanwhile that adopting a foreign royal title was not that charged in Roman Empire/Republic where sometimes even republican officials could receive a royal title from local barbarian tribes as a sign of loyalty. Thus it could be argued that even after Heraclius the power was in theory delegated to the emperor by the three forces combined: the people, the army and the church (the first emperor whose coronation involved the Patriarch though was that of Leo I the Thracian, before Heraclius).
The eastern title "King of Kings" was not religious in nature though. It just meant the king was recognized as the supreme king by other peer kings.
If we look deeper in the history, the ancient Greek kings were just gens elders. Take for example, Sparte where initially was four and later two tribes with their respective "kings", the two considered the equal kings of Sparta. I think the most ancient concept of "king" was exactly that of a tribe's elder, the head of a family.