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:
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:
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.