Flying cats are actually already in the game. Back in the Planar Chaos days I used this one in a really trollsy black deck:
http://gatherer.wizards.com/Pages/Card/Details.aspx?name=mir...
http://gatherer.wizards.com/Pages/Search/Default.aspx?action...
My neural network is telling me that it's actually too good at 4 mana.
Don't forget about potential combos like having a bunch of zero cost creatures in your graveyard + anything else that triggers when you play a spell or when a creature enters the battlefield. But even without that, this is a card advantage machine.
What zero-cost creatures did you have in mind? Those aren't incredibly common. And in any case, a combo that requires 3-4 specific cards is not overpowered; one that only requires 2 specific cards often is.
Even the synergy with Fume Spitter is pretty great. :)
It wouldn't be particularly broken in draft anyway - which is the only meta where rarity does impact balance to some extent.
FWIW, it's about the same cost as Enduring Renewal.
For that matter, creatures are cards, and there are effects powered by discarding cards or cards going to the graveyard, so if you can play one spell to get 5 more cards in your hand, and then discard 5 cards to get an effect...
> 2BB
> Legendary Creature - Cat
> Flying
> Whenever you cast a spell, you may return target creature card from your graveyard to your hand.
> 2/2
That's actually a fairly plausible card, in terms of mechanics. It's thematically appropriate for black, it's about the right cost, it's powerful but specialized (returns creature cards only, and only to hand rather than to play), and it's legendary to avoid multiplying its effect. This would work well in a deck with many creatures with "enters the battlefield" effects (common in black, as well as blue and red which are often used together with black), as well as many ways to sacrifice cards. Would even work as the general in an EDH/Commander deck.
The only thing slightly odd is the flavor: it's a flying cat. And with the right art (and perhaps a "black cat crossing your path" joke in the flavor text), that could work quite well.