On Google books, the earliest incident of "another think coming" is 1873. Certainly it was in spoken language before that.
Originally Posted by Rana_pipiens
"You think I ought to thank you for butting in and keeping me from dying without knowing anything about it, don't you? Well, you got another think coming." ... from the American Publishers Weekly - 1873
In the same source, the earliest hits for "got another thing coming" are in the 1960s, later than the OED citations.
It's on the basis of its word play that I believe the "think coming" version was first. It seems to me that sayings of this sort are built around and even motivated by catchy word play and rhymes.