Balin's ability works? When encounter deck is just empty and he cancels a shadow?

I think you should be able the resolve the entire first sentence completely, so you can cancel the shadow. Then, because the encounter deck is empty, you cannot, and therefore will not, deal and resolve a new shadow card.