Is "a whole nother" grammatical?

Actually, this is an example of what's called "tmesis". It is the insertion of a word into another word. In "a whole nother" the "a" and the "-nother" go together and the "whole" is slotted between them.

It is exactly the same process you get with the common, but more vulgar,

"Abso-fucking-lutely" or "unbe-fucking-lievable".

For a humorous take on the subject: xkcd.

Regarding "a whole other"

"A whole other" is a very common formulation; it is perfectly fine, use it if you wish. "A whole nother" is a very common formulation; it is perfectly fine, use it if you wish.

The thing about "a whole other" is that it's actually quite strange. According to etymonline.com it was way back in the 13th century that "an other" was combined into "another". "Another" is now a separate word in its own right. In fact, it is the word of choice. You will rarely find "an other thing", "another thing" is pervasive.

That's the thing about "a whole nother", it isn't the mistaken analysis that you have "a" and "nother" - it's the insertion of one word "whole" into a second (single) word "another". And that second word is "another", with an "n". This process intensifies "another". Compare:

"Here's another apple" - here we are talking about an apple. It is much like all the other apples that have been discussed. Our speaker is pointing out an unremarkable apple, an apple like many others before it. It's just another one.

"Here's a whole nother apple" - now we have a very different kind of apple. Perhaps, before, we only had red apples, but now we have a green apple. This isn't just another apple, like its fellows - this is a whole nother apple.

In reality, you'd be more likely to have something like "here's another apple" (points to an apple) and then "here's a whole nother fruit" (points to an orange).

"A whole other" is a different process. What is the difference? "A whole other" is like "fucking unbelievable." "A whole nother" is like "unbe-fucking-lievable".

With "a whole other", then, we have a whole nother thing going on. Firstly, we have "another" separated again, into "a" and "other", as it was prior to the 13th century. We also have "whole" qualifying "other". This is a little unusual. Consider, for example, "the whole other". There's nothing wrong with this, but this has fallen out of fashion. "A whole other" is quite a new formulation, relatively speaking, and one can't fail to notice that it's rare to have words qualifying "other". We could have "the good other books", but we prefer not to. We prefer "the other good books", or "the other, good books". (In the first case we have books that are good - like the other ones - and in the second we have books that are good - unlike the other ones).

This may explain why "a whole nother" comes along shortly after "a whole other", as @CupawnTae explains.

So: "a whole other" is a very common formulation; it is perfectly fine, use it if you wish. In fact, I find both "a whole other" and "a whole nother" very interesting, very cool, very valuable bits of English. I don't much have a problem with either of them. But, to argue that "a whole other" must be gramatically correct, because the word is "other", not "nother", seems to me to be a mistake. In fact, the word is "another". And the insertion of "whole" into "another" is a process relating to word-formation, to vocabulary, not to grammar. Admittedly, though, the spelling "a whole nother" is a little bit of a red herring. "A-whole-nother" would be more revealing.

I always took this usage to be purely humorous. Certainly I've only ever used it as such.

It's definitely not a contraction of "a whole another" - no one would say that (I hope). It's simply taking "another" and putting "whole" in the middle as if it was originally "a nother kettle of fish", which of course we know it's not.

The correct version is simply "a whole other".

EDIT: some more discussion on this here: "A whole nother" way of looking at things

Ultimately, "a whole nother" is the reverse case of "an unwashed apron." Some English speakers treat "another" as a compressed version of "a nother" rather than of "an other," and the adjective "whole" simply slips in between the presumed article (a) and the presumed noun (nother).

The opposite split is on display in the case of "an unwashed apron": napron arrived in Middle English from the Middle French word naperon, a diminutive of nape (cloth), according to Merriam-Webster's Eleventh Collegiate Dictionary (2003). But owing to what the Eleventh Collegiate calls "false division of a napron," English speakers produced "an apron"; the adjective "unwashed" then slips into place between the revised article (an) and the revised noun (apron).

Because "a nother" is making its way in a (relatively) literate world crowded with written guides to and interpretations of proper English, it doesn't have as easy a path to acceptance before it as "an apron" did; but the process in spoken English is much the same, I think, except that here the false division yields "a" instead of "an" as the associated indefinite article.

A somewhat similar operation underlies the U.S. dialect word druthers (meaning "preferences"), which seems to have come into existence at the end of a process in which "I'd rather" was altered by the Southern Appalachian pronunciation of rather as ruther, and then rebroken as "I druther."

Nother used here is just a folksy synonym for another, paired with a folksy saying; it's not necessarily ungrammatical, just very informal. Some people write it with the apostrophe, like 'nother, to indicate that they're explicitly contracting "another".

You wouldn't want to replace it in your example of a whole nother kettle of fish, because that would disrupt the folksy tone, which is the entire point of the idiom. But if you insist, a grammatical substitute would be something like an entirely different kettle of fish.