Clement of Rome, Clement of Alexandria, and Didymus the Blind said things that could be mistaken for the formula, but don't fit all the criteria. The first one to use it unmistakably is Origen, in passing, followed by Augustine, also in passing, though he frequently says other things that are near-hits. It's not until the Protestant Reformation that the formula becomes ubiquitous.
Early approximations and misses
Clement of Rome (d. c. 100), in his letter to the Corinthian church, commends them by stating a connection between their faith and virtue. At least two English translations (Lightfoot and Hoole) have Clement say that their faith is "virtuous," while one (Keith; ed. Donaldson, Roberts) has him phrase it as "fruitful of virtue." I don't believe the Greek justifies the latter translation, or at least not for our purposes in this question, but I thought it worth a mention since Keith's translation seems at first glance to apply so strikingly (if one grants a correspondence between "virtue" and "good works").
Clement of Alexandria (150 - 215) implies that neither love nor good works could exist without faith as their "foundation":
Love, on account of its friendly alliance with faith, makes men believers; and faith, which is the foundation of love, in its turn introduces the doing of good.
Stromata, Book 2, Chapter 6
According to Didymus the Blind (313 - 398), faith accomplishes two things, salvation and good works:
A person is saved by grace, not by works but by faith. There should be no doubt but that faith saves and then lives by doing its own works, so that the works which are added to salvation by faith are not those of the law but a different kind of thing altogether.
Commentary on James 2:26b via the Ancient Christian Commentary series, page 34; no full English translation is available
Origen (185 - 254), contemporary of Clement of Alexandria, explicitly identified faith as the root out of which the fruit, good works, grows:
This faith, when it has been justified, is firmly embedded in the soil of the soul like a root that has received rain, so that when it begins to be cultivated by God's law, branches arise from it that bring forth the fruit of works. The root of righteousness, therefore, does not grow out of the works, but rather the fruit of works grows out of the root of righteousness, that root, of course, of righteousness that God also credits even apart from works.
Commentary on Romans 4.1.18
Augustine of Hippo (354 - 430) uses the formulation at least once, seemingly borrowing from Origen, and close variants a number of other times.
In one place he speaks of faith as having "fruits," but does not explicitly identify them:
Each one sees his own faith in himself. He does not see but believes faith to be in another. And he believes all the more firmly, the more he sees faith's fruits that it is accustomed to work through charity.
On the Trinity, Book 13, Chapter 2 (link is to a different translation)
In another place, he states that good works "proceed from" faith (and that both faith and good works come from God), but does not use the word "fruit":
Works proceed from faith, and not faith from works. Therefore it is from Him that we have works of righteousness, from whom comes also faith itself
On Grace and Free Will, Chapter 7
But elsewhere he borrows two images from Origen: that of good works as a structure rising from the foundation of faith (Origen, Romans, 4.1.5) and the one that chiefly concerns us, good works as the fruit which spring from the root of faith:
I have nothing but praise for the superstructure of action, but I see the foundation of faith; I admire the good work as a fruit, but I recognize that it springs from the root of faith. ... If faith is devoid of the will to love, it will equally be devoid of good actions. But do not spend too much time thinking about the works that proceed from faith: add hope and the will to love to your faith, and you will have no need to ask yourself what kind of works you should perform.
Exposition 2 of Psalm 31:3-5
Just as Augustine borrowed the image from Origen, the reformation leaders undoubtedly borrowed it from Augustine. A sampling of the earliest uses in Protestant confessions will follow.
The Augsburg Confession (1535), Article 20, and Scots Confession (1560), Chapter 13, both say that the cause of good works is our reception of the Holy Spirit by faith. These two, according to the parameters of the question, do not use the formulation.
But later confessions would use the formula explicitly, while demonstrating their substantial agreement with the previous two. The Belgic Confession (1561), Article 24, compares good works to fruit and says that they proceed "from the good root of faith," which "regenerates us and makes us new creatures, causing us to live a new life and freeing us from the slavery of sin." The much later Westminster Confession (1646), Chapter 16, calls good works "the fruits and evidences of a true and lively faith," and states that the ability to do them is "wholly from the Spirit of Christ."
Similarly, the Second Helvetic Confession (1564), Chapter 16, says that faith "brings forth good fruit of all kinds, and good works," (the distinction, if any is intended, is unclear) and that "good works grow out of a living faith by the Holy Spirit" and "are done from God's grace through the Holy Spirit."
The characteristically terse 39 Articles (1563), Article 12, says without elaboration that good works "are the fruits of Faith, and follow after Justification."
Origen was the first to use the formula, building on Biblical teaching and imagery. It was then picked up by Augustine, whom the Reformation leaders consciously emulated, using it frequently. Since then, it has been widely used by Protestants.
However, it is also clear that whenever such authors were given the chance to expound on their meaning, they say "that good works are the fruits or result of salvation, or of love for God, or of God working within a person, and so on," often within sentences of using the formula.
I'm heavily indebted to We Believe in the Holy Spirit, ed. Joel C. Elowsky, particularly the section "The Giver of Life: In Justification," from which I got most of the church fathers quotes.