The idiom seems to have first come into use in the early 1800s. Charles Dickens, one of the most famous British writers, used it in his novel The Pickwick Papers in 1837. Prior to that, the idiom was "I'll eat my words." I would guess that eating one's own words was not a terribly unpleasant situation, since words are composed of air. To say "I'll eat my hat" suggests that you are much more sure of yourself, so you're willing to risk a much more unpleasant fate.