This is a question about part b) of the question. Below I'll show the major 'results' in my attempt at the solution, as well as where I got stuck:
1.
I defined a new $\mathcal{L}$-structure $\mathcal{N}$ defined as follows:
The universe is $\mathbb{N}\times\mathbb{Q}$ with $\hat{U}_{i}^{\mathcal{N}}=\{i\} \times \mathbb{Q}$ and $s_{i}$ defined in the usual way.
Intuitively, $\mathcal{N}$ acts the same as $\mathcal{M}$ and therefore one would expect $\mathcal{M} \prec \mathcal{N}$.
I have proved that to prove b), it suffices to show $\mathcal{M} \prec \mathcal{N}$.
2.
In my attempt to use the Tarski-Vaught test, I managed to prove a weaker result:
If $\mathcal{N} \models \phi(a,\bar{b})$ where $\phi$ is quantifier free, $a\in N$, and $\bar{b}\in M$ then there exists $a'\in M$ such that $\mathcal{N} \models\phi(a',\bar{b})$.
In part a), we are given that $T$, which is the full theory of $\mathcal{M}$ has quantifier elimination. Thus, if we can show that $Th(\mathcal{N})$ has quantifier elimination, as it should have, we can use the above result to complete the Tarski-Vaught argument and show that $\mathcal{M} \prec \mathcal{N}$.
The problem:
I am unable to show that $Th(\mathcal{N})$ has quantifier elimination, neither do I know how to show that $T=Th(\mathcal{M})$ has quantifier elimination either. I first tried to prove it by construction and failed. And then I used methods from 3.1 and found them inapplicable.
At this point, I have three options:
Find a way to show that $Th(\mathcal{N})$ has quantifier elimination
Find some other way to show that $\mathcal{M} \prec \mathcal{N}$
Scrap my previous ideas and try again to construct $2^{\aleph_{0}}$ non-isomorphic models of $T$.
Any hint or suggestion of where to go from here would also be greatly appreciated. Thanks for the read.
Just a bit of setup first, to make sure we are aiming for the same kind of proof here (I suspect you have something like this in mind when you say that $\mathcal{M} \prec \mathcal{N}$ suffices to prove (b)). For any subset $J \subseteq \mathbb{N}$ we define an $\mathcal{L}$-structure $\mathcal{N}_J$ with universe $(J \times \mathbb{Q}) \cup ((\mathbb{N} - J) \times \mathbb{Z})$. Then the interpretation of $U_i$ will be $\{i\} \times \mathbb{Q}$ if $i \in J$ and $\{i\} \times \mathbb{Z}$ otherwise. In particular, your structure $\mathcal{N}$ is then $\mathcal{N}_\mathbb{N}$, and $\mathcal{M}$ is just $\mathcal{N}_\emptyset$.
The goal will now be to prove that
Point 1 should be easy to see since an isomorphism between $\mathcal{N}_J$ and $\mathcal{N}_{J'}$ restricts to an isomorphism between $U_i^{\mathcal{N}_J}$ and $U_i^{\mathcal{N}_{J'}}$ for all $i \in \mathbb{N}$.
Point 2 comes down to the problem you describe in your question. Probably the easiest way to solve this, is to work with Ehrenfeucht-Fraïssé games. The winning strategy should be roughly as follows: every element player 1 picks will be in some $U_i$, player 2 then always picks an element from the $U_i$ in the other structure. If player 1 picks an element that is not of integer distance to any previously element picked in $U_i$ (either because no elements in $U_i$ have been picked yet, or because player 1 picks an element in $\{i\} \times \mathbb{Q}$), player 2 can respond with any element (in the $U_i$ of the other structure). If player 1 does pick an element that has integer distance from a previously picked element, then this determines precisely which element player 2 has to pick in the other structure. This proves point 2.
Since there are continuum many subsets of $\mathbb{N}$ and they all give us a model (by point 2) of $T$, and all these models are pairwise non-isomorphic (by point 1), we have indeed that there are $2^{\aleph_0}$ many different countable models.
If you really want to work with elementary embeddings, then I think showing quantifier elimination for every $\mathcal{N}_J$ is the best way to go. That should be doable, but it can get tedious.