While I haven't specifically tried to edit levels (due to lack of interest) I know how I would do it for NES games.
In FCEUX I'd set a write breakpoint for the part of the nametable that will be changed, and see where the game got that info from. Then I'd change what I find to see what does what. As for using a hex editor to edit the levels, sure, that's the old school way, but as Squall said, an actual editor with a GUI would be a better option, especially if you're going to make a whole new pack of levels.
I think I'll test out my theory soon and see how it goes.
But if that utility mentioned above lets you provide details about any game and then edit levels, that would be awesome, far better than an editor that only edits, say, Super Mario Bros (or JTS for that matter).
EDIT: that CadEditor looks pretty cool. I do, however, think it'd be better to have a system where you can add the games yourself based on your own hacking knowledge. This is fine if you're a total n00b who just wants to have fun making new levels for a popular game, but if you're someone like me who could do it with a hex editor but just doesn't want to spend the time, a more flexible one would be good. I wouldn't want to have to say "please mister, can you add support for Obscure Famicom Game?"