B737-900 Captain reported a ground conflict during taxiout and stated low visibility winter conditions contributed to the event.

Narrative

When we boarded Aircraft X in ZZZ at gate X; visibility was changing rapidly from VFR to an RVR of 1;000. My FO was new to the B737 and had just come off 'high-mins' but was very familiar with ZZZ airport. I intentionally slowed down the briefing process and used the pilot reference card to brief the low visibility departure procedure and we reviewed the low visibility taxi routes.The push-crew pushed us back from gate X onto [the] taxiway tail East. I set the brakes with gate Y at our two o'clock position and abeam Taxiway XX. While the FO was starting the #2 engine; I was paying close attention to Aircraft Y that had just cleared Runway XXR and was taxiing directly toward us on Taxiway XX. With the reduced visibility; I was concerned Aircraft Y did not see us. Aircraft Y slowed and turned onto Taxiway XY. When the Aircraft Y was no longer a threat; I turned my attention to the push-crew while the FO started the #1 engine. At this time; I noticed Aircraft Z pushing back from gate Y toward our aircraft. I was unable to transmit on the busy ground control frequency so I switched to comm2 (ZZZ OPS frequency) and made an urgent call for the aircraft at gate Y to hold their push. Aircraft Z heard our call and stopped their push-back. By the time Aircraft Z stopped; they had pushed back far enough that we were unable to taxi forward for fear our wingtip would hit Aircraft Z's tail. We asked Aircraft Z to pull back into gate Y so we could proceed to the runway.Aircraft Z informed us they had a tow Captain in training and that a supervisor was coming out to see what was going on. From our perspective; at no time did the wing-walkers involved in the push from gate Y alert the tow captain to our presence (taxi wands remained pointing up).High turnover rates in ground personnel positions; low visibility/winter operations; passenger COVID related compliance issues; extremely high reserve pilot utilization rates; lack of management's ability to resolve contract issues. All these threats and distractions are too prevalent in today's operations. What do we do when we have a threat? As professional pilots; we mitigate it. I slowed down the operation to fully utilize all the tools available to me (low visibility briefing card; asked dispatch for a take-off alternate; ensured my FO was ready for a low visibility departure; prevented a near ground mishap). It takes a team to have a safe operation. The 'team' needs to do better at mitigating threats.