The phrase to chew nails and spit rust is applied to someone who is very strong and resilient in the face of hardship or pain—cf. (as) tough as nails.

These are the earliest occurrences of to chew nails and spit rust that I have found, in chronological order:

1-: From a letter that one Charles Dickson wrote about life at the United States Naval Training Station at Newport, Rhode Island—letter published in The Daily Notes (Canonsburg, Pennsylvania, USA) of Tuesday 26^th February 1918:

We don’t have to worry about buying eats, as they give us all we can carry away without bending over, and when we go ashore, which will be tomorrow (Sunday) we will get lots of good eats, like home stuff, and feel satisfied, all for 50 or 60 cents. But even at that we can eat almost anything. We are getting so hard we can chew nails and spit rust.

2-: From an article by J. V. Fitz Gerald, published in The Washington Post (Washington, District of Columbia, USA) of Tuesday 2^nd March 1920—Nicholas Altrock (1876-1965) was a U.S. baseball player and comedian:

Tampa, Fla., Mar. 1.—[…] The brand of weather the last few days has put Nick Altrock down for the count. The comedian, who admits he is tough enough to chew nails and spit rust, went on a hunting trip over Sunday. He was gunning for wild, wild animals and came back with a fine cold. Cough medicine comes high and is scarce hereabouts, so all Nick is doing is taking the rest cure.

3-: From the column Over the Percolator, published in the Democrat and Chronicle (Rochester, New York, USA) of Monday 17^th November 1924:

Bright Sayings of the Children.
Contributed to Over the Percolator by A. M. L.
Do your Bit.

Jamie saw his neighbor doing some carpenter work. The man had nails in his mouth and finally decided to smoke a cigar. He bit off the end and spat it on the ground.
“Mr. B— chews nails and spits rust,” was Jamie’s report.

4-: From a letter by one Harry Levi, quoted in the boxing column On the Button, by Harry Bullion, published in The Detroit Free Press (Detroit, Michigan, USA) of Saturday 3^rd January 1925:

“Dear Harry:
[…]
““Ding” Digwall is still in training for his forthcoming match with Jackie Wolf, the herpicide champ ¹. “Ding” put in several hours yesterday putting the spots on blank dominoes.
“Jackie Wolf spent two strenuous hours watching the foul line in a bowling alley. Jackie sure is tough. He chews nails, spits rust and shaves himself with a blow-torch. Compared to Jackie, Mt. Vesuvius in action is just a placid mill stream.”

¹ I have not discovered why Jackie Wolf is described as “the herpicide champ”. The noun herpicide is from Latin herpes (from Greek ἕρπης, meaning shingles, literally a creeping) and the suffix -cide, denoting a person or substance that kills. Herpicide was coined at the end of the 19^th century by Dupont Morse Newbro (1865-1924), owner of Newbro Drug Company, a wholesale drug business in Butte, Montana. Dupont M. Newbro promoted the theory that a bacterium or parasite was the cause of dandruff, which then led to baldness. He claimed to have worked with a bacteriologist to create a formula that would kill the “dandruff germ”, hence the name herpicide that he gave to the hair restorer he produced.—source: the Smithsonian.

The phrase to chew nails and spit rust is used in British English, too. The earliest occurrence that I have found is from Blacko Notes, published in The Leader (Nelson, Lancashire, England) of Friday 28^th July 1933—Blacko is a village in Lancashire:

Last Thursday evening the recreation ground was the scene of a good deal of uproarious amusement. The cause of all the frolic was a cricket match which was being played between the tacklers from David Tattersall’s and Blacko. One of the worthy tacklers was a real “tough guy.” He looked as though he was “chewing nails and spitting rust.”

The second-earliest British-English use of to chew nails and spit rust that I have found is from an article by Denis O’Sullivan about the French bicycle racer Marcel Guimbretière (1909-1970), published in the Daily Mirror (London, England) of Tuesday 12^th April 1938:

They’re tough in the town of Sables D’Olommes [sic] ². . . . Cut their hair with barbwire clippers. Chew nails and spit rust. Laugh like they meant to bust the local seismograph. Are buried standing up. . . . So I’ve heard. . . .
Well, besides Tiger Clemenceau ³—who ran France in the war—a guy named Marcel Guimbetriere [sic] was born there.

² Les Sables-d’Olonne is a seaside town in Vendée, a département in west-central France, on the Atlantic Ocean.
³ The French statesman Georges Clemenceau (1841-1929), nicknamed Le Tigre (The Tiger), served as Prime Minister from 1906 to 1909 and from 1917 until 1920.

I have found an isolated use of to chew nails and spit rust in Australian English—it is from a theatrical review published in The Telegraph (Brisbane, Queensland) of Monday 17^th June 1929:

Nat Phillips ⁴ and his “Whirligigs” Revue Company burlesque a recent talking motion picture at the Empire Theatre this week. When they began the new programme at the Saturday shows they presented “In Very Old Arizona.”
[…]
The Radio Six do some pretty dances and a speciality by Sylvia Gardner, Eve Fennelly, and Marjorie Vause found favour. It is a story of “bad men,” so bad that one declared it was his pastime “to chew nails and spit rust.” Someone stole the sheriff’s mare; Six-shooter Sam (Nat Phillips) is accused; there is a dramatic cutting of cards to decide his fate, and a burlesque revue has a burlesque ending.

⁴ Nathan Robert ‘Nat’ Phillips (1883-1932) was an Australian comedian, theatre director, producer and revue company leader.