I understand that the letter "J" is relatively new — perhaps 400–500 years old. But since there has long been important names that begin with J, such as Jesus, Joshua, Justinian, etc., and which predate the introduction of a special letter, does that mean that the "J" sound predated the letter, or were such famous names spelled and pronounced differently?
The answer to this is.... complicated.
The letter J is, as you mentioned, relatively recent, and originated as a variant of the letter I. Why that happens is a little complicated, and requires unpacking some assumptions in your question.
In the original languages (Latin, Greek, Hebrew) which provide us with the names Jesus, Joseph, Justinian, etc., the sound which we write as J was pronounced as the English letter Y. (Just to make things confusing for English speakers, the phonetic symbol for this sound is [j].) In Latin, the letter for this was I/i, in Greek it was Ι/ι (iota), and in Hebrew it was י (yod). Thus, the Greek spelling for "Jesus" was Ιησους, pronounced something like "Yeh-SOOS", and the Latin likewise was Iesus.
Subsequently, in the Latin alphabet the letter J was developed as a variant of I, and this distinction was later used to distinguish the consonantal "y" sound [j] from the vocalic "i" sound [i]. However, at about the same time there was a sound change in many of the languages of Western Europe, such that the "y" sound changed into a "j" sound ([dʒ], or sometimes [ʒ]). So we have it that in English, the letter J now represents a consonant [dʒ] which is not obviously similar to the vowel [i], despite the fact that they descend from the same letter and the same sound. (English also has many [dʒ] sounds spelled with J which come from native Germanic roots.)
You can see this history worked out differently in the spelling systems of German and many of the Slavic languages of Eastern Europe, where the letter J spells the "y" sound [j], and the letter Y, if used at all, is primarily used as a vowel.
As @Laure mentions, this really belongs to the Linguistics group as this is a wider question pertinent to Latin and all/most Latin-influenced European languages.
Classical Latin did not have a distinct J sound (the J as we know in English.) When I was followed by another vowel, it usually sounded similar to English /Y/. Thus we had Iulius which was as if you said /Yulius/ or /Yulyus/.
In the Middle Ages, a new letter was assigned to this sound - J. However, it can be seen from even a casual glance that there has been widespread confusion of this and related sounds in many Western European languages.
In Spanish, for example, the /y/ sound moved to the letter /LL/, whilst the letter J picked up the guttural /ch/ which is due to possible Arabic influence.
In English meanwhile, an original prevocalic (i, e) /g/ sound palatalized to /j/ and eventually to /y/. We can see these when we compare Dutch or German cognates.
Yesterday - Gestern
This outline only partially touches upon the question asked, but I hope throws some light on the evolution of the sounds around the letter J in a broader context.
The quick answer is "yes" to both questions. Before j became differentiated from i, the "J" sound could be spelled with g in various combinations (edge, gem, exaggerate, etc.); and in ancient times, the names you mentioned were pronounced with an initial "Y" sound. Transcribed from Hebrew, Jesus was Yeshua. The Romans would have spelled Justinian "Iustinianus."
Just for fun - in Italian there is no "J" letter. The sound of that letter in English is represented by "ge" or "gi" as in Giovanni ("jo von nee" in crude English phonetics). You also see this in "gelato" and it shows up in the English "gelatin" and its shorter form "gel". See also "gemini", "gesture", "gentle", "gee whiz", "german", and lots more.
Who needs a "j"? The 'g' in "go" and "gu" are pronounced as in English ("hard" g). For a hard g sound followed by either "e" or "i", the Italians insert an 'h' between the 'g' and the following vowel. We use these spellings in english words like 'ghost" and 'aghast' (although the 'h' would not be used in Italian since the following vowel already makes the "g" hard.
Along those same lines - in Italian the English sound of "ch" is represented (along with its following vowel as "ci" or "ce". Similarly to 'g', inserting an 'h' between a 'c' and either 'e' or 'i' makes the 'c' "hard" - as does a following vowel of 'o' or 'u'. And again we use some of this same stuff in English - 'echo', 'charisma', 'chimera', etc. I think most of those words in English come from Greek - just to confuse things - but the idea that a 'ch' is pronounced as 'ck' (or just "hard c") is difficult for English speakers to accept until they see the same rule applied in English.
Not really and English Language question... but interesting (to me) anyway.
I think that this letter has to do with the limitation of the alphabet that was used as the template. For example, the Armenian alphabet created in 405-406 AD, has 36 characters/letters originally and an additional 2 characters/letters were added in the middle ages. The original alphabet contained a character for the both the hard and soft "j" sounds. Also the Georgian alphabet (33 letters created in the 4th century AD) has a character for the hard "j" sound as in January and a character for the softer "j" sound as in a 'zh" as would be found in "Zha Zha Gabor". Since Georgian is not an Indo-European language while Armenian is an Indo-European language, one can come to the conclusion that the creation of the letter is dependent upon the needs of the language and not the language group.