Say I'm Running an Ally deck with a Kabira evangel out. Someone casts fatal push targeting it. I CoCo, Hit at least one Ally, call Pro Black. The Kibira Evangel still dies due to it already being cast and it being targeted before it had pro black, correct?
No. If Kabira Evangel has protection from black as Fatal Push resolves, it will be an illegal target for Fatal Push, so Fatal Push will fail to resolve because its only target is illegal (C.R. 702.16b, 608.2b).
EDIT (Dec. 15): Correctness edit.
EDIT (Apr. 27, 2018): Edited to conform to rule change in Dominaria.
EDIT (Jan. 1, 2019): Edited.
Target legality for an instant or sorcery spell is checked twice: once when the spell is cast, and again when it begins to resolve.
So, after you perform your play and Evangel's ability resolves, you and your opponent pass, so that Fatal Push starts resolving. At this point, the game checks the legality of Fatal Push's target, sees that Evangel is an invalid target because of its protection, and Fatal Push is countered by the rules instead.
EDIT (Dec. 15): Correctness edit.
EDIT (Apr. 27, 2018): Edited to conform to rule change in Dominaria.
EDIT (Jan. 1, 2019): Edited.
So, after you perform your play and Evangel's ability resolves, you and your opponent pass, so that Fatal Push starts resolving. At this point, the game checks the legality of Fatal Push's target, sees that Evangel is an invalid target because of its protection, and Fatal Push is countered by the rules instead.