The 2000 Palm Beach County ballot may be the first use of this for a presidential race. But I've found no evidence of a 1996 ballot as illustrated in the question. As there is no central repository of ballots across the US, it may not be possible to answer the question of when it was first used with any certainty.
Discussion
In 1965 the Votomatic data registering device was patented. The application for the patent was filed in 1962, so it may have been first used between those dates, however none of the photos from that era show the "butterfly" ballot style in use.
After the 2000 election, one of the inventors of the Votomatic system said they had anticipated the problem with using both side early on, and that they had rejected the concept.
A published paper titled The Butterfly Did It: The Aberrant Vote for Buchanan in Palm Beach County, Florida credits "innovation" of butterfly ballots to the supervisor of elections in Palm Beach County. The same article also does mention the 1996 election, bit without illustration nor apparent claim that it was a butterfly ballot. However it presents extensive analysis of the statistics of the 1996 election and comparing them to statistics of the 2000 election. They did not identify there was any anomaly in the 1996 voting. This the presence of this analysis might have led to confusion about the format of the 1996 ballot.
But by 2000 other jurisdictions were clearly using the butterfly style, possibly earlier, but other examples seem to be from races with extremely large numbers of candidates.. For example the book Design for Democracy: Ballot + Election Design by Marcia Lausen, discusses a Cook County, IL, judicial retention ballot, also in November 2000, which reportedly included 73 candidates and spanned 10 pages in Votomatic butterfly format. The author may have selected this example because it "interleaved" yes and no votes.
Lausen goes on to cite even earlier cases where an extremely large number of candidates may have caused ballot designers to choose poor layouts, dating as far back as 1969 (it is not clear if these were done on Votomatic equipment or butterfly style.)
Background Information

The following photo shows a Votomatic used in "butterfly" configuration in the 2000 presidential general election in Palm Beach County, Florida.

A portion of the 2000 Judicial Retention butterfly ballot pictured below. Image from Design for Democracy... book, copyright 2007 by The University of Chicago:
