TLDR: Only granting flying before blockers are declared stops non-fliers from blocking a creature.

In general, once blockers have been declared, there are only two things that can make an attacking creature no longer be blocked:

1. Some effect explicitly causes the attacking creature to not be blocked any longer. In this case, the attacker would do damage normally as if not blocked. I’m not aware of any cards that can actually achieve this.
2. Some effect causes the attacking creature to be removed from combat before damage would be dealt. In this case, the attacker deals no damage at all unless they somehow got some in before they were removed from combat (say, some attack trigger caused them to deal damage). A number of things can cause this to happen, most commonly somebody using a kill spell on the attacking creature when priority passes at the end of the declare blockers step.

Almost all cases are covered by rules 509.1g and 509.1h:

509.1g Each chosen creature still controlled by the defending player becomes a blocking creature. Each one is blocking the attacking creatures chosen for it. It remains a blocking creature until it’s removed from combat or the combat phase ends, whichever comes first. See rule 506.4.

509.1h An attacking creature with one or more creatures declared as blockers for it becomes a blocked creature; one with no creatures declared as blockers for it becomes an unblocked creature. This remains unchanged until the creature is removed from combat, an effect says that it becomes blocked or unblocked, or the combat phase ends, whichever comes first. A creature remains blocked even if all the creatures blocking it are removed from combat.

Your described case may seem at first to be a bit special, because the legality of a set of creatures blocking is technically checked before you get to that point in the declare blockers step. Because of this, we also have the following in rule 509.1b:

509.1b: The defending player checks each creature they control to see whether it’s affected by any restrictions (effects that say a creature can’t block, or that it can’t block unless some condition is met). If any restrictions are being disobeyed, the declaration of blockers is illegal.
A restriction may be created by an evasion ability (a static ability an attacking creature has that restricts what can block it). If an attacking creature gains or loses an evasion ability after a legal block has been declared, it doesn’t affect that block. Different evasion abilities are cumulative.

This means that gaining or losing flying, or shadow, or skulk, or some other similar ability does not affect whether the creature is blocking or not, even if this happens before 509.1g and 509.1h ‘lock in’ what creatures are blocking and what creatures are blocked.

However, that bit of 509.1b doesn’t actually matter in 99% of cases. In almost all cases, the earliest that you could grant an evasion ability is after all blockers are declared, all costs for blocking are paid, and all damage assignment orders are declared. Only then do triggered abilities that trigger on blocking happen, and only once those are on the stack does anybody get priority (thus making this the earliest anything could actually happen at instant-speed, including usage of activated abilities such as the one that allows Goblin Balloon Brigade to give itself flying).

The only exceptions to that are if you have some effect causing you to grant a creature an evasion ability as a cost for blocking (AFAIK no such effect exists in the game currently) or you have an effect imposing some other cost on blocking, and that cost triggers an ability that grants an evasion ability (I think this might be possible, but I’m not certain).