Short answer: You are under NES restrictions, but not without sprite overlays on three of them.
Optional long answer:
For backgrounds it's: 4 colors per 16x16 region. 4 palettes of 4 colors, but one of the colors must be used in all 4 palettes.
For sprites, 3 colors per 8x8 sprite. 4 palettes of 3 colors with transparency. Because sprites can be overlaid with transparency, one can get more colors in a region by overlaying sprites, but there are only 64 sprites and usually they're not all used for overlays during gameplay.
Here is how your first portrait would be constructed with sprite overlays:

It uses six sprites, one background palette, one sprite palette. The purple represents unused palette colors.
The guy on the pink background would need sprites anywhere there's white.
The dog works on only one background palette since it's only four colors throughout.
The rightmost portrait would need a lot of sprites. If you use sprites to overlay as the hair color, it's a lot. (I don't have time to get out my magnifying glass to see exactly how many at the moment.) For Green it's a lot because it's the color surrounding the head. For the bright skintone, still a lot, etc. The color used for the shirt looks like fewer, but since it's spaced all over it's probably be quite a few. This is the one I'd suggest rethinking if this were for an NES game.