Hypothetical situation: Player A has one creature and player B has also one creature. Now the player A casts a black spell to destroy the creature and targeting player's B creature. If creature B gets protections from black does the player A need to target the only possible target left in the game and that is his creature? What if the creature B would be returned to hand instead? Is it the same?
I am no Magic expert, but I think the answer is no.
The target is chosen and needs to be valid when the card is played. Then the stack system kicks in, so the state of the game can change. When the card is resolved, you check whether the target is still valid. If it is, the effect happens, if it isn’t, the effect does not happen. In fact, you are not allowed to choose a new target then, even if you want to.
From the basic rulebook, page 10:
When you see the word “target” on a spell or ability, you have to choose one or more things for the spell or ability to affect. You’ll be able to choose only certain kinds of things, such as “target enchantment” or “target creature or player.”
You choose the targets for a spell when you cast it, and you choose targets for an activated ability when you activate it. If you can’t meet the targeting requirements, you can’t cast the spell or activate the activated ability. Once you choose targets, you can’t change your mind later.
When the spell or ability resolves, it checks the targets to make sure they’re still legal (they’re still there, and they match the requirements stated by the spell or ability). If a target isn’t legal, the spell or ability can’t affect it. If none of the targets are legal, the spell or ability is countered and does nothing at all.
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.