How can I show RSA-OAEP is not IND-CCA secure if G always outputs 0 (i.e. there is no hash function)?
$b$ is random


Yes, but it is random in the set $\{0,1\}$. $b$ reflects the coin toss made by the decryption oracle / challenger in the IND-CCA game to decide if s/he encrypts $m_0$ or $m_1$ at the second bullet.


  Does $m_b \in \{b\mathbin\|m_1,\ b\mathbin\|m_2\}$ ?


No in general, and that holds even if we fix the indices to be in $\{0,1\}$ rather than $\{1,2\}$. The intended meaning of $m_b$ is:
$$m_b=\begin{cases}m_0&amp;\text{if }b=0\\m_1&amp;\text{if }b=1\\\end{cases}$$
otherwise said, $b=0\implies m_b=m_0$, and $b=1\implies m_b=m_1$. Thus $m_b \in \{m_0, m_1\}$ with no concatenation involved. Note: the IND-CCA game allows to choose the two messages $m_0$ and $m_1$ equal, but that's a silly move.