That's not strictly true - 'Caesar' was not, as commonly believed, one of those Roman nicknames given to an individual, but rather one of those Roman extra names designed to mark out branches of a family. Taking another famous Roman name, it was like the 'Scipio' in L. Cornelius Scipio Africanus, not like the 'Africanus'. As it happens, the famous Caesar had a father, grandfather and great-grandfather all named C. Iulius Caesar. However, you've hit the bigger nail on the head - people tended to be creative with which names were used in order to make sure that they could tell important people apart. We still have traces of that today - we know one emperor as Tiberius (the praenomen) and another as Nero (the cognomen), which avoids the confusion of having two called Tiberius.
EDIT: Looking through the internet for evidence on this, I came across Gaius Julius Caesar Strabo Vopiscus, a distant relative who somehow ended up with two cognomina, despite not having any relatives with either or immediate relatives called Gaius.