So say I had an original NES game that was not a ROM hack and had completely original code, graphics, music, gameplay, characters, etc. Would I be able to sell it legally as long as it didn't have the Nintendo name on it?
Unless hundreds of people are breaking the law out in the open on eBay, then yes, it's legal. What made you think otherwise (what law could you possibly be breaking)?
AFAIK, all hardware patents related to the NES have already expired, so you can safely release NES cartridges (even NES clones are legal now, look at retroUSB's AVS). Just don't use anyone else's software, characters or assets and you should be fine.
As for gameplay, I'm pretty sure it's safe to copy large portions of other games' gameplay as long as the end result looks different enough to not be mistaken for a version/port of another game.