You can't, for example, use one palette on the upper half and another palette on the lower half?.
Short answer: Not really.
A character in an NES or GB game is usually made of multiple sprites which can be 8x8 or 8x16. The individual sprites are assigned their own palette, but they're basically going to share the same palette anyway. The NES Megamans and Super Mario Bros. 2 use overlay sprites to give the characters' faces some extra color like this hack with the Stardroids.
Since GBC has 8 palettes for sprites, it's remotely possible to redraw a character using two or more palettes, but that creates the problem of ensuring your color choices are supported in all scenarios, regardless of what's being drawn on screen.
Megaman Xtreme 1 and 2 have gorgeous backdrops but their sprites are pretty meh.