Calvin

The first extant writing to contain the phrase is John Calvin's Antidote to the Council of Trent (1547).

First, for context, Calvin was responding to Canon 11 of the sixth session of the Council of Trent (which you can read at the above link):

Whosoever shall say that men are justified by the mere imputation of Christ's righteousness, or by the mere remission of sins, exclusive of grace and charity which is shed abroad in their hearts by the Holy Spirit, and is inherent in them, or also, that the grace by which we are justified is only the favor of God, let him be anathema.

Calvin replied:

I wish the reader to understand that as often as we mention Faith alone in this question, we are not thinking of a dead faith, which worketh not by love, but holding faith to be the only cause of justification. (Galatians 5:6; Romans 3:22.) It is therefore faith alone which justifies, and yet the faith which justifies is not alone: just as it is the heat alone of the sun which warms the earth, and yet in the sun it is not alone, because it is constantly conjoined with light.

Lutheran confessions

A similar phrase is found in the Epitome of the Formula of Concord (1577), 3.11, one of the confessional documents of Lutheranism, written by a group of early Lutheran theologians including Martin Chemnitz:

But after man has been justified by faith, then a true living faith worketh by love, Gal. 5:6, so that thus good works always follow justifying faith, and are surely found with it, if it be true and living; for it never is alone, but always has with it love and hope.

Luther himself

Fred Lybrand, who disagrees with the quote, wrote in his 2009 book Back to Faith (pp. 4-5) that he has been unable to find it in Martin Luther's writings, but he believes that Luther likely said it.

Luther's 1535 commentary on Galatians 5:6 may be of help here, since that's the verse referred to in the above statements by Calvin and the Book of Concord:

Faith must of course be sincere. It must be a faith that performs good works through love. If faith lacks love it is not true faith. Thus the Apostle bars the way of hypocrites to the kingdom of Christ on all sides. He declares on the one hand, "In Christ Jesus circumcision availeth nothing," i.e., works avail nothing, but faith alone, and that without any merit whatever, avails before God. On the other hand, the Apostle declares that without fruits faith serves no purpose. To think, "If faith justifies without works, let us work nothing," is to despise the grace of God. Idle faith is not justifying faith. In this terse manner Paul presents the whole life of a Christian. Inwardly it consists in faith towards God, outwardly in love towards our fellow-men.

Luther also speaks on this concept in his Third Disputation Concerning Justification, written in 1536, which can be found in volume 34 of Luther's Works. I found the quote in Six Points on Luther's "Epistle of Straw" by James Swan. Catholics said that if sola fide is true, then you could say, "Faith without works justifies, Faith without works is dead [Jas. 2:17]. Therefore, dead faith justifies." Luther answered:

The argument is sophistical and the refutation is resolved grammatically. In the major premise, "faith" ought to be placed with the word "justifies" and the portion of the sentence "without works justifies" is placed in a predicate periphrase and must refer to the word "justifies," not to "faith." In the minor premise, "without works" is truly in the subject periphrase and refers to faith. We say that justification is effective without works, not that faith is without works. For that faith which lacks fruit is not an efficacious but a reigned faith. "Without works" is ambiguous, then. For that reason this argument settles nothing. It is one thing that faith justifies without works; it is another thing that faith exists without works.

According to Roland Bainton's biography of Luther, Here I Stand, Luther wrote at one time:

Faith is a living, restless thing. It cannot be inoperative. We are not saved by works; but if there be no works, there must be something amiss with faith.

Bainton's citation for this purported Luther quote is simply VIII, 361. I do not know what this refers to, so if anyone could comment below and let me know where it comes from, it would be much appreciated.

Regardless of the source of that last quote, there's a wealth of other similar Luther quotes. See footnotes 101 and 103 on page 246 of The Theology of Martin Luther by Paul Althaus for a few more examples.

Conclusion

So in summary, we have no record of Luther saying it, but the idea is present in his writings, and his followers used a variation of the phrase. The earliest recorded use of the phrase itself is by Calvin.