No, you don't get to choose new targets, and the spell will likely be countered.
You choose targets as part of casting a spell or activating an ability, before it's actually put on the stack. (The full list of steps for casting spells and activating abilities is rule 601; the short summary in most cases is that you announce the spell, pick targets, pay the cost, and place it on the stack.) Once targets are chosen, they stay chosen, unless you have a spell like Redirect that explicitly changes them.
When a spell or ability tries to resolve, if all its targets are no longer legal, the spell is countered. Simple as that, no new targets. The targets could become illegal if they've changed zones (like a creature going to the graveyard or being exiled), if they were granted protection from the spell's color, if they gained hexproof, or perhaps no longer meet some restriction the spell has for its targets.
However, if the spell has multiple targets and at least one is still legal, the spell still resolves, doing as much as it can. For example, if it said "destroy two target creatures" and one is still a legal target, that one would be destroyed.
Here's the relevant rule, with added emphasis:
608.2b If the spell or ability specifies targets, it checks whether the targets are still legal. A target that's no longer in the zone it was in when it was targeted is illegal. Other changes to the game state may cause a target to no longer be legal; for example, its characteristics may have changed or an effect may have changed the text of the spell. If the source of an ability has left the zone it was in, its last known information is used during this process. The spell or ability is countered if all its targets, for every instance of the word "target," are now illegal. If the spell or ability is not countered, it will resolve normally. However, if any of its targets are illegal, the part of the spell or ability's effect for which it is an illegal target can't perform any actions on that target, make another object or player perform any actions on that target, or make that target perform any actions. The effect may still determine information about illegal targets, though, and other parts of the effect for which those targets are not illegal may still affect them.
For example, if Feast of Blood targets a creature that gains protection from black, Feast of Blood will be countered as it would resolve for having only illegal targets. You will not gain any life.
On the other hand, if just one of the creatures targeted by Hex gains protection from black, the other five will still be destroyed.