Ok, so I know I'm not the first person to think about this, but what is Shadow, really? As a character article, he's a rat. And he's in the rat category. But I have an argument against this. Shadow shows intelligence rats just don't possess. I mean, I'm not saying that rats can't be intelligent (ex. Cluny the Scourge), but many rats show that they are just dumb soldiers. But Shadow seems to act more like a mercenary. Next, is his reliability. Cluny, when he hires Shadow, talks as if he has a history with Shadow. And he probably does. Shadow appears to be an expert thief, spy, and mercenary. If Cluny succeeded in capturing the Abbey, he probably would have made Shadow his right-hand-man. Or rat. Or weasel. Or whatever. Third, is his speed, Shadow shows the ability to climb and run much faster than a rat could. He even overpowers Matthias when he catches him in the act. Now a rat is about 50% bigger to twice as big as a mouse, but in many cases, a mouse, if it is a large and aggressive one, such as Matthias, can kill a rat. However, there is not much of a struggle between Shadow and Matthias before he pulls the tapestry away, showing that Shadow is not a rat. More likely a mustelid of some sort, such as a weasel.
My final thought here is that Shadow is not a rat. Nor is he a weasel. Or not a "pure-bred" weasel, at least. My thought is that he could be a Wearat, considering he is cunning,fast, and quite evil, or most likely a part rat, but mostly weasel. Hybrids such as these have been confirmed to exist. Example: A weasel-rat hybrid is born, it's mother being a weasel. Animals raised by other animals will likely mate with other animals of that kind, so this Wearat does. His offspring are one-third rat. The offspring of them are one-fourth rat, looking much like a weasel with maybe a rat's thin legs. Now, on to why Shadow is black-furred. There are two possibilities here: One, being that the original hybrid's rat father was a black-furred rat, not uncommon in many places, and the gene was passed down to the rat's great-grandchildren, the one-fourth rats. Two, being there was a meloninistic mutation, causing Shadow, and maybe even all of his siblings to be black-furred, or at least very dark brown-furred.
That is my theory.