$\mathbb{Z}_m^*$ is the set of elements $x\in\mathbb{Z}_m=\dfrac{\mathbb{Z}}{m\mathbb{Z}}$ such that $x$ has a multiplicative inverse.
The question supposes that $\mathbb{Z}_m^*$ is not a cyclic group.
$\\$
$\mathbb{Z}_m^*$ is nevertheless a finite abelian group.
Every finite abelian group is isomorphic to $\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}$, where the $q_i$ are all prime powers. This decomposition is unique up to an ordering of $q_i$. This is the fundamental theorem of finite abelian groups.
See, for example, this link.
I am going to call this a fundamental decomposition.
$\\$
We want to evaluate $\displaystyle\prod_{y\in\mathbb{Z}_m^*}y$, right?
Re-expressing $\mathbb{Z}_m^*$ as the above direct sum,
we simply need to evaluate $S=\displaystyle\sum_{r\in\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}}r=(s_1,\ldots,s_k)$
where $s_i\in\mathbb{Z}_{q_i}$ and $s_i=\displaystyle\left(\prod_{j\neq i}q_j\right)\times\sum_{t\in\mathbb{Z}_{q_i}}t$.
Notice that for an odd prime power $q$, we have $\displaystyle\sum_{a\in\mathbb{Z}_q}a=0$. This means that if $q_j$ is an odd prime power for a given $j$, then $s_j=0$.
Instead if $q$ is an even prime power, i.e. if $q=2^h$, then $\displaystyle\sum_{a\in\mathbb{Z}_q}a=2^{h-1}$. Observe that $2\times2^{h-1}=0$ in $\mathbb{Z}_q$. Therefore, if you are given $i\neq j$ such that $q_i$ and $q_j$ are both even prime powers, then $s_i=0$ and $s_j=0$.
$\\$
Therefore, we would like to prove that the condition in the question, namely that $\mathbb{Z}_m^*$ is not a cyclic group,
implies that in the fundamental decomposition $\mathbb{Z}_m^*\cong\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}$,
there exist $j_1\neq j_2$ such that $q_{j_1}=2^{h_1}$ and $q_{j_2}=2^{h_2}$.
$\\$
Let $m=p_1^{a_1}\ldots p_n^{a_n}$, where the $p_i$ are distinct primes.
Due to the Chinese Remainder Theorem,
$\mathbb{Z}_m^*\cong (\mathbb{Z}_{p_1^{a_1}})^*\oplus\ldots\oplus(\mathbb{Z}_{p_n^{a_n}})^*$.
Recall that the size of $(\mathbb{Z}_{p^a})^*$ is $\phi(p^a)=p^{a-1}(p-1)$, which is an even number except when $p^a=2$.
Furthermore, if $G=H_1\oplus\ldots\oplus H_n$, the fundamental decomposition of $G$ is equal to the direct sum of the fundamental decomposition of each $H_i$.
Also, if $p$ divides the size of $H$, then one of the terms in the fundamental decomposition of $H$ will be $\mathbb{Z}_{p^a}$ for some $a\geq 1$.
$\\$
Therefore, if you can find $i\neq j$ such that $p_i^{a_i}\neq 2$ and $p_j^{a_j}\neq 2$, then the fundamental decomposition of $(\mathbb{Z}_{p_i^{a_i}})^*$ will have a term of the form $\mathbb{Z}_{q}$, where $q$ is some power of $2$. You can say the same for $(\mathbb{Z}_{p_j^{a_j}})^*$.
This will be enough to show that $S=(0,\ldots,0)$.
The only cases left to check are:
- $m=p^a$ or $m=2p^a$, where $p$ is an odd prime and $a\geq 1$. But as you have stated in your question, you already know that there is a primitive root $\text{mod}(m)$ in these cases, which you can therefore ignore.
- $m=2$ and $m=4$, which you can also ignore.
- $m=2^a$ for $a>2$. In this case, refer to this Wikipedia entry to see why $\mathbb{Z}_2\oplus\mathbb{Z}_2$ is a subgroup of $\mathbb{Z}_m^*$. Notice that $\mathbb{Z}_2\oplus\mathbb{Z}_2$ is not a subgroup of $\mathbb{Z}_{2^h}$. Therefore, in the fundamental decomposition $\mathbb{Z}_m^*\cong\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}$, there must be $i\neq j$ such that $q_i$ and $q_j$ are both powers of $2$.
$\\$
$S=(0,\ldots,0)$ corresponds to $\displaystyle\prod_{y\in\mathbb{Z}_m^*}y=1$,
because $(0,\ldots,0)$ is the identity element in $\mathbb{Z}_{q_1}\oplus\ldots\oplus\mathbb{Z}_{q_k}$,
and $1$ is the identity element in $\mathbb{Z}_m^*$.
