Earlier Derivation
I have found the phrase "hermeneutics of the letter" in a quote within John Catalano's Francis Lieber: Hermeneutics and Practical Reason (2000) on page 26. On page 24, we find out the quote is an English translation from the German of G. A. Friedrich Ast (1778-1841) in his book Grundlinien der Grammatik, Hermeneutik und Kritik (1808), which (if my Google translate skills are working) is the last paragraph of section 82 (page 192 of this online version).
The block quote in Catalano's work, in context of some of Catalano's writing around it, is this (bolding added; bracketing in the inner block quote is Catalano's, in the outer is mine):
There are three elements to any explication of an ancient passage. [Catalano now quoting translation of Ast...]
The letter, meaning, and spirit are therefore the three elements of explication. The hermeneutics of the letter is the explication of the word and subject matter of the particular; the hermeneutics of meaning [Sinn] is the explication of its significance [Bedeutung] in connection with the given passage; and the hermeneutics of the spirit is the explication of its higher relation to the idea of the whole in which the particular dissolves into the unity of the whole. (Sect. 82: 48)
The first (hermeneutics of the letter) involves "grammatical and historical knowledge of antiquity" (Sect. 83: 48). One must study languages (including grammar and etymology), archeology, and history in order to accurately explicate the letter of the text. The second (hermeneutics of meaning) involves a psychological understanding of the author. Some meanings are simple while others are allegorical. ... The third (hermeneutics of the spirit) is an explication of the guiding idea of the passage. The author may or may not have been conscious of that idea. "For the idea is the higher, living unity from which all life evolves, and to which it returns again spiritually transfigured" (Sec. 85: 49).
Conclusions
Regarding your particular question:
- The English phrase is earlier than Peter Leithart's 2009 work, since Catalano's is 2000. There may be earlier still out there... and in fact just found another English work from 1990 referring to Ast, The Hermeneutic Tradition: From Ast to Ricoeur (Gayle L. Ormiston and Alan D. Schrift, eds.), using the phrase on page 12.
- The phrasing in German words, "Die Hermeneutik des Buchstaben," is at least nearly two centuries earlier with Ast's 1808 statement. I do not have time to pursue if it is even earlier than Ast as a German phrase, and what the meaning may have been in that earlier work.
- Given Catalano's supplemental quotes of Ast, this phrase appears to be a reference to grammatical/historical hermeneutic to understand the statement of the passage itself, contrasted with both (1) any significance the statement makes from the original author's perspective and (2) a higher spiritual concept that the original author may not be aware of. The whole approach is related to, though not exactly parallel to, the fourfold sense of Scripture approach, and thus the phrase "hermeneutics of the letter" may not exactly parallel a grammatical/historical hermeneutic, which generally is against an "allegorical" or "spiritual" meaning in most cases.
- I have not read Leithart's Deep Exegesis: The Mystery of Reading Scripture, so I cannot say for sure how in-line he is with this historical assessment of the phrase's usage, but perhaps you can now assess that given the information here. It could be he is using the phrase the same way, or in a "novel" way to his own approach.