Can a creature be destroyed just before Shalai gives it hexproof?
Yes, you can destroy the creature before it gains Hexproof.

Shalai's ability is a static ability which does not take effect until after casting Shalai resolves (i.e. the spell leaves the stack and Shalai enters the battlefield).604.2  While Shalai is still on the stack, the static ability is not "active" and has no effect.

Before Shalai resolves, Player A is given priority and can then use Walking Ballista's ability, which is also placed on the stack.  This ability will resolve before Shalai, killing the 1/1 creature before Shalai can give it Hexproof.