This is homework for a class I didn't take, but which is a prerequisite for a course I will take. In particular I supposed it's something other people may see as a homework problem in the future.
Prove that there is a linear order $(M, <)$ such that $(M, <) \equiv (\mathbb{Z}, <)$ and such that there is an embedding $j : (\mathbb{Q}, <) \to (M, <)$.
My current solution is the following, which I believe is essentially correct.
Let $M = \mathbb{Q} \times \mathbb{Z}$ with the lexicographic ordering $(q, n) < (q', n')$ iff $q < q'$ or $q = q'$ and $n < n'$. Since this is a discrete ordering on a countably infinite set with no endpoints, it should be elementarily equivalent to $(\mathbb{Z},<)$. (I think this is true but I haven't actually proved it yet.) On the other hand, we can take $j : \mathbb{Q} \to \mathbb{Q} \times \mathbb{Z}$ to be $j(q) = (q, 0)$ and clearly we recover the usual ordering on $\mathbb{Q}$.
I would be glad to have either verification that the above works or a heads-up that it doesn't, but the context leads me to believe there's a better argument using the Downward Lowenheim-Skolem theorem. Is there? If so, any tips on how to get there?
Let $\mathcal{L} = \{<\}$. Let $T = \text{Th}(\mathbb{Z}, <)$. $T$ is a complete $\mathcal{L}$ theory.
Let $\mathcal{L}' = \mathcal{L} \cup \{c_q : q \in \mathbb{Q}\}$, where $c_q$ are new constant symbols.
Let $T'$ be the following $\mathcal{L}'$ theory:
$T \cup \{c_r < c_s : r < s\}$.
Using an appropriate expansion of $(\mathbb{Z}, <)$ to a $\mathcal{L}'$-structure in order to apply the compactness theorem, one obtains a $\mathcal{L}'$-structure $\mathcal{M}$ such that $\mathcal{M} \models T'$.
The reduct of $\mathcal{M}$ to $\mathcal{L}$ which we also denote by $\mathcal{M}$ is a model of $T$. Since $(\mathbb{Z}, <) \models T$, $\mathcal{M} \models T$, and $T$ is complete as a $\mathcal{L}$-structure, $\mathcal{M} \equiv (\mathbb{Z}, <)$.
Clearly, $j : \mathbb{Q} \rightarrow \mathcal{M}$ is given my $q \mapsto c_q^{\mathcal{M}}$.
More generally, $(\mathbb{Z}, <)$ can be replaced by any infinite linear ordering by the same proof.
In regard to your original construction, it is indeed true that the two structures $(\mathbb{Z}, <)$ and $\mathbb{Q} \times \mathbb{Z}$ are elementary equivalent. This follows from the fact that discrete linear ordering without endpoints is a complete theory (Proposition 2.4.10 in Marker's $\textit{Introduction to Model Theory}$). This is proved using a game like the Eurenfeucht-Fraisse Games. Note that these two structures are not isomorphic. Your construction will work.
Also observe that the $\mathcal{M}$ constructed above is not necessarily countable. However, using the Downward-Loweinheim Skolem, you can find a countable elementary substructure of $\mathcal{M}$ which would also suffice.