There's an article in the Coming Home Network about the Rule of Faith. In it there are several interesting quotes from Church Fathers on the topic, let me select a few:
From St. Basil the Great's De Spiritu Sancto (circa AD 375) we have (emphasis mine):
Of the dogmas and kergymas preserved in the Church, some we possess from written teaching and others we receive from the tradition of the Apostles, handed on to us in mystery. In respect to piety both are of the same force. No one will contradict any of these, no one, at any rate, who is even moderately versed in matters ecclesiastical. Indeed, were we to try to reject unwritten customs as having no great authority, we would unwittingly injure the Gospel in its vitals; or rather, we would reduce kergyma to a mere term.
Epiphanius, Bishop of Salamis (circa AD 315–circa AD 403) writes (again, emphasis mine):
However, none of the sacred words need an allegorical interpretation of their meaning; they need examination, and the perception to understand each proposition’s force. But tradition must be used too, for not everything is available from the sacred scripture. Thus the holy apostles handed some things down in scripture but some in traditions, as St. Paul says, ‘As I delivered the tradition to you,’ [1 Cor 11:2] and elsewhere, ‘So I teach, and so I have delivered the tradition in the churches,’ [1 Cor 4:17] and, ‘If ye keep the tradition in memory, unless ye believed in vain.’ [1 Cor 15:2].
Regarding the Magisterium of the Church, we have St. Irenaeus (died circa AD 202) writes in Adversus Haereses:
Since therefore we have such proofs, it is not necessary to seek the truth among others which it is easy to obtain from the Church; since the apostles, like a rich man [depositing his money] in a bank, lodged in her hands most copiously all things pertaining to the truth: so that every man, whosoever will, can draw from her the water of life. For she is the entrance to life; all others are thieves and robbers.
Also St. Augustine (AD 354–AD 430), in his epistle against Manichaeus:
For my part, I should not believe the gospel except moved by the authority of the Catholic Church. So when those on whose authority I have consented to believe in the gospel tell me not to believe in Manichaeus, how can I but consent?
I concede that in none of these quotes we see the three pillars enumerated, but certainly the doctrine is to be found at the very least in the Fourth Century, even if not explicitly stated.