Where did とんでもない (meaning "not at all" or "outrageous!") come from?
Could it be 飛んでもない? ("will not even jump/fly" in a similar way how "When pigs fly" is considered a remark for something outrageous?)
Or is there a more complete sentence from which とんでもない was taken out?
It has nothing to do with flying. Tondemonai derives from an older todemonai. Some speculate that the initial to is to be identified as 途 (to, "road"). While you may want to further break it into to demo nai, there is little evidence to support this so you should treat it as a single word. That being said, modern re-analysis of the final nai into a separate morpheme is quite common resulting in tondemo arimasen, a supposedly more polite form.
Rough extraction/translation from http://gogen-allguide.com/to/tondemonai.html:
Originally from 途{と}でもない, 途{と} meaning "way", "road", "path". Combined with adjective 無{な}い, this becomes 途{と}でもない "off the path".
