I found two early instances of "holy Toledo"—one from 1908 that seems to be merely coincidental with the later exclamation, and one from 1928 that seems to be the real deal. From the Monroe City [Missouri] Democrat (March 5, 1908):
The Toledo Blade [a daily newspaper] says. "We would rather sit and wait two months for rosy-cheeked spring to come [to] Tintinnabulous Toledo than eat strawberries all winter in Heavenly Houston." How about preferring to pluck ice cream sodas in Holy Toledo during the visit of ruddy-cheeked summer than to look for a cool place in Thermogenic Houston during the same period. —Ex.
And from The Saturday Evening Post, volume 200 (1928) [combined snippets]:
Whatever insight the adopted girl gained of her foster father's character came to her through observation—and the stars bear witness that there was plenty to observe. When he had been in regular service no one had ever noted McIntosh, engineer on 1 and 2, holding mugging parties with his oil can or stroking a polished main rod with a loving hand. He had never been known to do anything but be disagreeable and growl constantly and bring his train in on the money despite hell or high water. But when he went cut on pension, holy Toledo!
The instance from Thomas Johnson, Red War (1936) that medica cites in her excellent answer is actually one of two occurrences in that book. Here they are in somewhat fuller context:
The manager was wringing his hands, apparently on the verge of tears. "It is terrible, terrible, Herr Bayne, that this should have happened. No doubt there have been Communist riots somewhere. Alas, I fear no one will come back to see you now."
But in this prediction the manager was wrong, for almost as he finished speaking a great booming voice was heard in the wings. "Holy Toledo, officer, I don't savvy your lingo. All I want is to ...
"You seem to know everything, Mr. McWade."
"Holy Toledo, I wish I did!" groaned the Westerner. "But there ain't one of us can figger out what's up—except somebody's in for a swell double crossin'."