How can we efficiently and unbiasedly decide which children to generate in the expansion phase of MCTS?
The first thing to consider in this question is: what do we mean when we talk about "generating a child/node". Just creating a node for a tree data structure, and allocating some memory (initialised to nulls / zeros) for data like deeper children, visit counts, backpropagated scores, etc., is rarely a problem in terms of efficiency. 

If you also include generating a game state to store in that node when you say "generating a node", that can be a whole lot more expensive, since it requires applying the effects of a move to the previous game state to generate the new game state (and, depending on implementation, probably also requires first copying that previous game state). But you don't have to do this generally. You can just generate nodes, and only actually put a game state in them if you later on reach them again through the MCTS Selection phase.

For example, you could say that AlphaZero does indeed generate all the nodes for all actions immediately, but they're generally "empty" nodes without game states. They do get "primed" with probabilities computed by the policy network, but that policy network doesn't require successor states inside those nodes; it's a function $\pi(s, a)$ of the current state $s$ (inside the previous node), and the action $a$ leading to the newly-generated node.



But if you're really sure that, for your particular problem domain, the generation of nodes itself already is inefficient, then...


  [...] This is clearly biased in favor of children earlier in the stream.


Yes, you would get a significant bias with such a stream-based approach, probably wouldn't work well.


  [...] This may be harder to implement than the previous version because computing the number of children may be as hard as computing the children themselves. [...]


Again I agree with your observation, I don't think there are many problems where this would be a feasible solution.


  I believe that if the number of iterations of MCTS remaining, X_t, is larger than the number of children, N, then it doesn't matter what you do, because you'll find this node again the next iteration and expand one of the children.


This would only be correct for the children of the root node. For any nodes deeper in the tree, it is possible that MCTS never reaches them again even if $X_t &gt; N$, because it could dedicate most of it search effort to different subtrees.



I think your solution would have to involve some sort of learned function (like the policy network in AlphaZero) which can efficiently compute a recommendation for a node to generate, only using the inputs that are already available before you pick a node to generate. In AlphaZero's policy network, those inputs would be the state $s$ in your current node, and the outward actions $a$ (each of which could lead to a node to be generated). This would often actually be very far from unbiased, but I imagine a strong, learned bias would likely be desireable anyway if you're in a situation where the mere generation of nodes is a legitimate concern for performance.