Here's an even earlier appearance of a variant of the first stanza:

San Francisco Chronicle (Aug. 7, 1898), p. 3:

From the halls of the Montezumas
To the shores of Tripoli,
We have fought our country's battles
On the land and on the sea.
For our duty ever ready,
We are the bravest ever seen,
And we glory in the title
Of United States Marine.