The other don't have Nova whatsoever and can defeat Novas as well
I don't believe that

Care to hint at what this super-deck's combo is?

The only potential weakness of Nova decks that I can see, is that creatures are often cast in groups. On your first turn for instance, if get a great hand you can play 1-2 Novas followed by four or even five creatures. In the mid-game, you often have a "dead hand" of 3 or 4 creatures you can't summon, then you draw a Nova and summon them all on the same turn.

I would look for cards that affect a lot of creatures at once:

Thunderstorm deals 1 damage to each creature.
Rain of Fire is like Thunderstorm x3.
Plague is a mass infection.
Fire Shield deals out the same effect basically.
Gravity Shield is a mass freeze for big creatures.
Dimensional Shield is a mass freeze for all creatures.
Ice Shield can freeze lots of creatures.
Procrastination Shield forces 50% freeze.

etc.

I know using Nova-Air I have often seen the computer play two Lycanthropes and a Rustler, then I wiped them out with a Thunderstorm

What I really, really, really doubt is that a deck built around mass effects (probably a Fire-Death deck) would be FAST enough to beat Nova without using Nova itself.