Caesar was never tribune of the plebs. More importantly you're making the common mistake of thinking that the patrician order is synonymous with the Roman aristocracy--it is not at all. The Conflict of the Orders ended a good three or four hundred years before Caesar lived, and the plebeian nobility had been fully integrated into the senatorial class by the end of the Punic Wars. Indeed, they made up the vast majority of it. We know of around 50 patrician families in the early Republic--by Caesar's lifetime only 14 still had surviving patrician lines, though some still survived in plebeian lines. Patricians are in fact relatively rare from the second century on, and the patrician order essentially ceased to exist during Caesar's civil war, resulting in the need to promote plebeian senatorial families to patrician rank in order to keep certain priesthoods alive. Plebeians could and did hold essentially all the magistracies patricians did (the singular exception is the aedileship, which was technically split into plebeian and curule varieties, though the difference was largely immaterial). In fact, one of the seminal events of the Conflict of the Orders was the passage of the Lex Licinia, which established by law the need to elect at least one plebeian consul per year. In some years there were two plebeian consuls, and the majority of the nobiles, those with consular ancestors, were plebeian. Cicero, the Gracchi (descended from the ancient plebeian gens Sempronia) Octavian (prior to his adoption), Antony, Pompey, Crassus, Lucullus (both he and Crassus were descended from the oldest and most important of the plebeian senatorial clans, the gens Licinia), Hortensius, Cato, Brutus, Cassius--these are plebeian names, and only Cicero is a novus homo. Indeed, you almost have to go out of your way to find patricians by Caesar's lifetime, the order had long ceased to have any real distinction other than birth.

There was no actual law that Marius violated by standing for the consulship multiple times, nor was there such a law when Tiberius Gracchus announced his intention to stand for tribune for the second time. Nor was Marius the first to stand for the consulship multiple times, or the first to break the ten year tradition. Titus Quinctius Capitolinus Barbatus supposedly held the consulship six times between 471 and 439. As early as 508/507 Publius Valerius Puplicola was supposed to have held the consulship twice in succession. Even if we suppose those two to be legendary we find plenty of consuls holding the office multiple times or within only a few years of each other. Papirius Cursor was consul five times between 326 and 313 (and was dictator in 324 and 309). Valerius Corvus was consul five times between 348 and 300. Six times if we include his suffect consulship in 299, and three of those consulships were between the years 348 and 343.

Here's the thing. The Republic had no such thing as a public prosecutor. It was nobody's job to find wrongdoers and indict them on behalf of the state. Instead accusation was brought by private citizens and then proceeded through either civil or criminal action. Which means simultaneously that even if multiple terms had been illegal (which they were not) violation of such a law might not have been acted on and that even if they hadn't been illegal technically speaking one could prosecute for some other reason or on a nebulous charge of some kind of unlawful activity. Calpurnius Piso was recalled from his province and despite Cicero's delivery of the In Pisonem in 55 was not prosecuted for extortion, a trumped-up charge intended to get at Caesar. In a more relevant case, Opimius, the consul responsible for C. Gracchus' death, was prosecuted by the tribune P. Decius the next year for the unlawful execution of Roman citizens without trial. Opimius successfully argued that the senatus consultum ultimum, which had been used for the first time during his consulship, granted him extraordinary powers and that he therefore had the right to ignore the statute against unlawful execution. There was no law regarding the senatus consultum ultimum at all, and its powers did not exist before 121. Yet Decius prosecuted on the basis of a related law, and though no law was ever able to regulate the SCU a means of prosecuting its abuse was still found. In such cases as when no specific law applied it was up to the jury to decide whether such an action as was being prosecuted was to be considered unlawful