"Justification" is the wrong phrasing. Ultimately, the methods by which one interprets the Torah, the list of rules that we use to get from rather-confusing-text to coherent-set-of-rules, are supposed to be those communicated to us from Moshe, who got them directly from God. There are of course certain wrinkles - one, for instance, is the fact that different Tannaim had different lists of rules, and one of the ones that had Gzeira Shava in it (as far as I know there were only two such competing lists, and it may have been in both; I don't know the details) was vindicated by history. It must be noted at this point that one of the assumptions in Judaism is that an omnipotent god will make sure that the correct version of his laws is the one that is vindicated by history.
Regarding the validity of the Oral Torah in general, there's a famous story in which Hillel is approached by a convert who wanted to learn only the Written Torah because he didn't trust the Oral Torah. Hillel being Hillel, he accepted the man's request and began by teaching him the Hebrew alphabet - א is the letter aleph, and so on. The following day he says, "Let's review what we learned yesterday" and says א is the letter bet. The convert, naturally, objects, to which Hillel replies, "Isn't what you're saying right now part of the Oral Torah?"
The object lesson being, of course, that the difference between "how to even pronounce the words written here" and "what the finer points of a particularly complex rule of Biblical exegesis are" is just a matter of degree.
I personally take a mathematical approach to Judaism based on the above principles. Judaism is like geometry. We have the Rambam's thirteen principles of faith (one of which attests the veracity of the text of the Torah) - call these our axioms. We have Rabbi Yishmael's thirteen rules of exegesis - call these our rules of inference. All of the rest of Judaism flows logically from that, just as all of the rest of Euclidean mathematics flows logically from Euclid's five original axioms and the laws of logic. If you switch out Rabbi Yishmael's rules of exegesis for Rabbi Akiva's, or switch out the Rambam's thirteen principles of faith for, say, an alternative grouping that allows for corporeality of God (which used to be far more legitimate than it is now), you get non-Euclidean Judaism. Which, though it sounds like the domain of Cthulhu, is if you know mathematics an equally valid system in which to work.