You are correct that schooling was very different. Although forms of compulsory education existed beforehand, the first compulsory school attendance laws in the U.S.A. were passed in Massachusetts in 1838-1852 under the supervision of Horace Man. The first parlimentary act in Britain to my understanding was the Forster Education Act of 1870, so with respect to the "without leave" aspect. As a legal term, The Century Dictionary and Cyclopedia notes that it's mentioned in the provisions of the Elementary Education Act of 1876. It does not seem as needful when your attendance is left to the discretion and dealings of your parents, although perhaps influences other than government mandate may have influence over that. Much of the education was also performed by churches. However, despite this, the phrase is older as you have noted.
Also, the state of orthography was also largely unsettled before the influence of Thomas Dilworth, Samuel Johnson and Noah Webster. The main difficulty is that there seems to be many variations of the phrase involving various spellings. Additionally, the original form of the phrase is "Play the Truant" which follows the pattern of many other English phrases such as Play the Fool.
The first instance of "to play the truant" with that spelling of truant in the New English Dictionary (N.E.D) on Historical Principles, Volume 10, part 1 Ti-U (1926) is in 1834. There were certainly definitions that are earlier than that though. The Royal Dictionary Abridged in two parts written by Mr. Boyer in 1700 defines the phrase play the Truant as meaning,
"to ſeek Bird-Nests when one ſhould be found at School.
In 1728, we see the more nominal form in A Serious Reply to Twelve Sections of Abusive Queries, Proposed to the Consideration of the People Called Quakers; by Samuel Fuller of Dublin (a Quaker):
Is there no Sun in the Firmament? becauſe Men that are Blind, or that their Eyes cannot, or will not see it; or is a School Maſter unlearned or inſuſſicient, because any of his Lads play Truant and neglect his Reproof and Instructions &c.
Those are the earliest records I found of the phrase with the now standard spelling of truant, but the N.E.D. still beats it with alternatives. The quotation prior to the one from 1834 is from "1642 Rogers Naaman 93 That so they may shun this sharpe Schoolemaster by playing the trewants." which exemplifies one of the variant spellings. Searching for alternative origins on Google Books led me to this possible precursor:
But, as young Trewants, toying in the schools,
Inſteed of learning, learne to play the fools:
We gaze but on the babies and the cover,
The gawdy Flowrs, and edges guilded over;
And never farther for our leſſon look
Within the volume of this various book;
Where learned nature rudeſt ones instructs,
that by His wiſdome, God the World conducts.
Du Bartas His Diuine Weekes and Workes with a Compleate Collection of All the Other Most Delightfull Workes Translated and Written By... Josuah Sylvester and Th. Hudson. Ill by Van Dalen, R. Elstrack 1633
Additionally, one use of truant as an adjective is noted in 1615.
Yea good Gods! what a sight it is to behold an austere, Hee is no Philosopher that feares death.bushbearded Philosopher (who feares a razor, as much as a rope) quake at the name of death, euen as a treuant boy does at the name of his Tutor?
Heauenly DOG: Or the life and death of that great Cynicke Diogenes, who by Laertius is stiled Canis coelestis, the Heauenly Dogge, and Iouis filius, the sonne of Iupiter. by A. Stafford
The N.E.D. traces the phrase playing traunt itself back to 1560, which is probably what The Online Etymology Dictionary is referencing by 16th century, and Shakespeare notably uses the phrase at least couple of times right before the end of the 16th century in both The Wives of Windsor (1597) and Love's Labour's Lost(1598). However these usages of it do not seem to refer to students, but a more general sense of idleness and wandering from analogy with the indolent people. It seems as if the phrase was just starting to be applied to students at the beginning of the 17th century. The passage from Love's Labour's Lost seems like it might have influenced this type of usage though, since it mentions students and makes a point of inattentiveness:
Another of these students at that time
Was there with him: If I have heard a truth,
Biron they call him; but a merrier man,
Within the limit of becoming Mirth
I never spent an hour's walk withal:
His eye begets occasion for his wit;
For every object that one doth catch,
The other turns to a mirth-moving jest,
Which his fair tongue — conceit's expositor—
Delivers in such apt and gracious words,
That aged ears play traunt at his tales,
And Younger hearings are quite ravished;
So sweet and voluble in his discourse.