Well, the tribes may have played a role in the names of Germany. I suppose Allemange (french) was derived from a prominent germanic tribe called "Allemannen" which resembles the words "Alle Mannen", roughly translated it would equal "Everyone". Since that tribe was widespread and bordered on what is France today, the name might have indeed been used to describe everyone from around here.
Tysk? Well, I really don´t know, there were many dialects spoken in the early German times. Perhaps it was the name of a tribe in the north?
The Germans themself were only a tribe, but one that also became very prominent. Until the "Holy roman reich of german nation" (or something like that, I never tried to translate Heiliges römisches Reich deutscher Nation).
It then became commonly known as Germany.
This would be Germania in the german tongue (also the name of an ancient local goddess) but every German calls it "Deutschland"....
Well, but considering other countries names, they seem to be pretty consistent. There don´t seem to be so many discrepancies. Except the far eastern countries like China or Japan, which are called Zhonggou and Nippon by local inhabitants (But I don´t know how they are written in the native script)