http://www.worldwidewords.org/qa/qa-jum2.htm

"The phrase Jumping Jehoshaphat is first recorded from Mayne Reid's Headless Horseman of 1866, but is probably older." from above link.

I thought I remembered it as a favourite expletive of Yosemite Sam, but can find no proof.