How much would it have sold? Would the Gamecube have sold a bit/allot more? Would it affect Wii sales in any way? Would it somehow lead to Atari releasing a new console? 

Those are 5 questions that i can't/am too lazy to answer, but i think you can :)

Whoops, I thought it said SSB for some reason loll, Yea it maybe would have sold more

GC would've outsold the PS2, and the DS and the Iphone (all iterations), and Windows (all iterations) combined. In short, every single person in the world would, on average own more than one GC.

Would sell okay, but not Wii levels. NSMBWii sold a lot because you could combine it with Wii Sports and a newbie friendly controller. Easier to sell that.

Nothing different. NSMB was so revolutionary because it brought the new and the old generations together to play a remixed version of the old SM games on a Handheld port.

Nintendo thought NSMBWiiU would move consoles. They were sadly mistaken. Same would go for the GC...

Would probably sell N64 numbers.

It needed something like GTA exclusive in order to sell well. And I think Galaxy would have helped more than NSMB, despite their Wii numbers.

NSMB WiiU failed because there was nothing special about it

Mario games do best when they give the player an exciting new world to explore.

NSMB WiiU was anything but, it was pretty much a rehash of NSMB Wii (which itself was nothing special but benefitted from being the first 2D console Mario in over a decade, the market was ravenous for a new 2D Mario at the time, once that hunger was somewhat satiated, Nintendo needed to wow with its next iteration, it failed to do so)

NSMB on GCN would have done amazing, because of the hunger for a 2D Mario, but it probably would have sucked a lot of steam out of the Wii release (unless Nintendo had decided to put actual effort into the Wii version and not just rehash)

As a result GCN would have sold much better, but Wii sales would probably be about 10-15 million less

We just had a long thread on this in like June, if not more recently.
Wii sold NSMB just as much as NSMB sold Wii. Without them being tied together it wouldn't have had as great an impact. NSMB had the chance to sell so much because the Wii was already appealing to a wide demographic. Plus the GCN's controller is not very good for 2D platformers anyway.

And if the game was already out on GCN, then the next 2D Mario game on Wii would pull a NSMBU and sell less, as it would probably be too similar. How much less I do not know.

I'd guess GCN hits 35 million at the best case if NSMB released 2002-2004. I don't think it would affect Wii's sales much, no one was basing their decisions to purchase it off of how good/bad the GCN was.

Now, if NSMB was a launch game for GCN perhaps it could have changed the system's whole trajectory... still overshadowed by the PS2, though.

According to some folks, it did begin on the Gamecube. Remember, the Gamecube sold 130 million + units.