Many things indicate that the word had been on a long journey before it arrived in Scadinavia. Nubian 'kadis' and Berber 'kadiska', words both meaning cat, hint to a possible Afro-Asiatic origin. This makes sense, because the cat was most likely first domesticated in Africa or the Middle East, and was originally unfamiliar to the ancient Greeks and Romans. Perhaps the Romans also changed the name of the animal from felis to cattus/catta when they were introduced to the domestic cat.
When the cat came to Scandinavia we had other words for felines as well. In Norwegian these survive as lo and gaupe - the lynx. We will never know why didn't they use these words to describe the new, tame, miniature version, but it's doubtful that many purists will lose much sleep over it. The new animal brought economical and hygienic benefits, for example to farmers suffering from mice-infested granaries.
But what about all the other Scandinavian animals that have -katt as a suffix? Norwegian røyskatt, Swedish lekatt, and Danish lækattall denote the same animal; the stoat. Then there is the aforementioned igulkǫttr, which lives on as the Swedish word for hedgehog - igelkott. Ígull is an old Germanic name for the hedgehog, and le-/læ- may be an ancient word for stoat, while Norwegian røys-, meaning cairn, points to where the animal prefers to live. Some have also speculated that Freyja's cats in reality may have been stoats or weasels. European monkeys are comparably small, and as we know from before, monkeys are called "ape-cats" in Norwegian. Today we distinguish between apes, which are big, and monkeys which are small. What all of these animals have in common is the fact that they are small in size, and that they are mammals. Accordingly, we must assume that cat originally meant "a small mammal". Perhaps the reason why only the purring newcomer got the honor of being named cat without a prefix or suffix, is because they didn't know it by any previous name.