Historically, Greek hadn't have any kingdom ever, just many state-cities. Thus, Greece cannot have any "king" title.
That is not right. All Indo-European cultures spent centuries in a similar situation, living in small villages or tribes rather than in nations hundreds of miles long. And they all had words such as Latin "rex". Such words simply referred to the rulers of the social units the people lived in at the time. Greek does seem to have lost its cognate for that, but only because "baslieus" took its place.
Perhaps, "Basyleus" is Italian word "vassal", when a Roman Emperor pointed a Greek vassal to rule over the Roman province Greece?
This word occurs already in Mycenaean Greek as qa-si-re-u, then in Greek authors from Homer onward. There is no way it could have been borrowed from Italian.
But if Greeks don't know how the word "Basylious" was formed, maybe it is Romans' word? Greeks didn't name their kings as "caesars" but "vassals" of Rome, isn't it?
The point about the Mycenaean form of the word and its use by Homer is that it's chronologically impossible. The Greeks had this word long before the Romans had any influence in Greece. Mycenaean Linear B writing was used before 1200 BCE. Homer wrote sometime between the late 1100s and middle 800s. The Romans didn't arrive and conquer Greece until 146. At best, Rome might have been influential enough for the Greeks to notice and import something from them slightly before the conquest, around 200 or so, but, when Greeks started using this word no less than a thousand years before that, Rome was nothing to them.
Also, the sounds are wrong for an imported Latin word in Greek. Its oldest form, in Myceneaen, begins with a symbol (transcribed today as "qa") that represented both /kʷa/ and /gʷa/, before those initial consonant sounds shifted to /p/ and /b/ in Greek. It couldn't have gotten a /gʷ/ from Latin because Latin didn't have it. The Latin outcome of Proto-Indo-European /gʷ/ was /w/, which would have resulted in a Greek word beginning with a vowel, not [β]. (This doesn't eliminate the possibility that "basileus" and "vassal", which was pronounced "wassal" at the time, both came from the same PIE word beginning with /gʷ/.)
Do you think Arabic basil heroic/brave man and basaalah heroism have anything to do with the Greek word, a loanword maybe?
The oldest form starting with /gʷ/ makes it impossible for the Greek word to have been imported from a source with the initial /b/ already in place. If it's imported, the source needs to be one that would have yielded /gʷ/ before the gʷ→b shift. (This doesn't eliminate the possibility of Greek later exporting it with the /b/.)