there have been plenty of approaches of stylized characters with stylized shading, cell shading isn't the only thing you could do with normalmaps, it's totally possible i guess it depends on where you want to do it, are you just asking in general or do you want to apply it in a given engine/3dtool?
A normal map drives the forms and basic shading of a model, not just fine greeble detail. Your concern has more to do with texture resolution than anything related to a normal map. IE: you could probably use a lower res normal map with a cell shader. Even then, getting sharp details and such, not high-frequency but like…