Laudator Temporis Acti

Robert Hendrickson, Encyclopedia of Word and Phrase Origins, 2nd edition (New York: Facts on File, 2004), p. 728:

tooth and nail. The Latin equivalent for this ancient phrase was toto corpore atque omnibus ungulis, "with all the body and every nail." The French have a similar saying, too: bec et ongles, "beak and talons." All mean the same: to fight with tooth and nails, biting and scratching, with weapons, with all the powers at one's command. Figurative use of the expression in England brings us back to the early 16th century, and it was listed as a proverb then.

The Latin phrase occurs at Cicero, Tusculan Disputations 2.24.56 (toto corpore atque omnibus ungulis, ut dicitur, contentioni vocis adserviunt), where the ut dicitur shows that it was proverbial in his day.

I have not seen James Rogers, The Dictionary of Cliches (New York: Ballantine Books, 1985), but I find the following entry quoted on the WWW:

FIGHTING TOOTH AND NAIL - Fight fiercely, with all one's resources; cling tenaciously. A Latin proverb expressed this thought as 'dentibus et vnguibus.' In the sense of fighting, it appeared in English in 1562 in Ninian Winget's 'Certain Tractates': 'Contending with tuith and nail (as is the prouverb).' In the sense of holding fast, it is equally old, as in Erasmus' 'Enchiridion Militis Christiani' (1533): 'Take and holde this toth and nayle, that to be honour onely which springeth of true virtue.'

The Latin original of Erasmus' Enchiridion (9.5) does not use the tooth and nail phrase:

hoc mordicus teneto solum eum honorem esse, qui a vera virtute proficiscitur.

It's possible to find ancient equivalents closer to the modern English tooth and nail, e.g.

Lucretius 5.1284:

Ancient weapons were hands, nails, and teeth.

arma antiqua manus ungues dentesque fuerunt.

Lucian, Dialogues of the Dead 11.4:

But gold they would guard with teeth and nails and any other way.

τὸ δὲ χρυσίον ὀδοῦσι καὶ ὄνυξι καὶ πάσῃ μηχανῇ ἐφύλαττον.