The only result in Google Books is 2006's Brothers and Sons: An Epic Comedy Adventure by Dana Myrick:
"Holy crap on a cracker! That paint job would cost three or four thousand dollars in the city,” exclaimed John loudly. When John saw the expression on James's face, he knew he had said too much. “But, of course, they rip people off in the city, and you're not like that, are you Gator?" said John.
In Google Groups there's an older result from Jul 13, 2001 in by John in rec.music.phish:
Holy crap on a cracker!! I wish I could go!
There's a dozen "crap on a cracker" results, the oldest is apparently from 1992's Usher's Passing by Robert R. McCammon but there's no preview to confirm. The next is 1996's The Basement by Bari Wood:
"I'd say it was crap on a cracker, Reed. But what did happen to those bees?"
The oldest "Holy * on a cracker" from Google Groups is "Holy hell on a cracker!" from Oct 12 2000 in alt.roundtable.
The related "Jesus Christ on a cracker" can be found in 1993's Save me, Joe Louis by Madison Smartt Bell:
"Jesus Christ on a cracker," Macrae said. "You about killed me there."
Finally, as a bonus, here's what holy crap on a cracker looks like.