Well, as has been amply illustrated above, "Well, I never!" is short for a longer expression and take your pick for precisely what that longer expression is.

English's ability to shorten the too-long knows no limits. Well, yes it does. Probably the ultimate contraction has to be "halfpenny'sworth" chopped down to "haypth"! I think the English language has rather rested on its laurels since coming up with that one.