These are the earliest citations I could find for the phrase "loss of generality" in JSTOR. Note how they all slightly differ from the strict "without loss of generality" form. Also note how they're all from William R. Hamilton.
... and many of the new partial differential coefficients vanish, without producing, by this simplification, any real loss of generality
- Third Supplement to an Essay on the Theory of Systems of Rays, William R. Hamilton, The Transactions of the Royal Irish Academy, Vol. 17, (1831), pp. v-x, 1-144
Mr. Jerrard has therefore accomplished a very remarkable simplification of this general problem, since he has reduced it to the problem of discovering two real functions of two arbitrary real quantities, by showing that, without any real loss of generality, it is permitted to suppose ...
- On the Argument of Abel, Respecting the Impossibility of Expressing a Root of Any General Equation above the Fourth Degree, by Any Finite Combination of Radicals and Rational Functions, William R. Hamilton, The Transactions of the Royal Irish Academy, Vol. 18, (1839), pp. 171-259
And if we farther simplify the formulae by supposing $ a = 1, b=0, c=0, d=0$, which will be found in the applications to involve no essential loss of generality ...
- Researches Respecting Quaternions. First Series, William Rowan Hamilton, The Transactions of the Royal Irish Academy, Vol. 21, (1846), pp. 199-296
EDITED TO ADD:
Here are the dates and authors for the first 20 instances of "loss of generality" in the above JSTOR search:
1831 Hamilton
1839 Hamilton
1846 Hamilton
1848 Stokes
1854 Cayley
1855 Cayley
1856 Thomson
1857 Cayley
1860 Donkin
1862 Cayley
1863 Schlafli, as communicated (translated?) by Cayley
1864 Cayley
1866 Sylvester
1867 Cayley
1867 Cayley
1868 Cayley
1870 Strutt
1871 Russell
1873 Williamson
1874 Cayley
While the three earliest citations are due to Hamilton, fully half of the first twenty instances in the JSTOR database are due to Cayley. Of course, the JSTOR database is not comprehensive; in particular, it does not include The Transactions of the Cambridge Philosophical Society which contains the earlier Stokes citation that Brendan McKay found.