I have implemented the solution derived below using PyClaw in an IPython notebook. If you download that, you can adjust the initial values and see the computed solutions.
General setup
In the solution of a Riemann problem for the 1D Euler equations, there are generally 3 waves. Two of them are genuinely nonlinear; the other is a contact discontinuity, which only carries a jump in the density. My understanding is that you'd like to set up initial left and right states such that the velocity is initially zero everywhere, the rightmost wave is a shock moving at Mach number $M$ relative to the right-state sound speed, and the leftmost wave is a rarefaction (you didn't specify the last requirement, but it would make the problem analogous to the Sod shock tube). This situation is depicted in the figure below, which also establishes the notation I'll use.
Finding the state behind the shock
Let
$$\mu = \frac{2(M^2-1)}{M(\gamma+1)}.$$
Using the Rankine-Hugoniot conditions, we find that the state just to the right of the contact is given by the following:
\begin{align}
\rho_r^*& = \rho_r \frac{M}{M-\mu} \\
u & = \mu c_r \\
p & = p_r \frac{(2M^2 -1)\gamma+1}{\gamma+1}.
\end{align}
If you were willing to have a non-zero velocity for the left state, you could stop here and use the values just derived for the left state. If you want $u_l=0$, read on.
Finding the left state
Next, we know that the left state and the $[\rho_l^*, u, p]$ state must be connected by a left-going rarefaction. The relevant Riemann invariants imply
$$\rho_l = \frac{4\gamma p_l}{(\gamma-1)^2 u^2} \left(1- \left(\frac{p}{p_l}\right)^{\frac{\gamma-1}{2\gamma}}\right)^2$$
and
$$\rho_l^* = \left(\frac{p}{p_l}\right)^{1/\gamma} \rho_l.$$
So we can prescribe any value we like for $p_l$ and compute the remaining values $\rho_l,\rho_l^*$ from the equations above. The only catch is that the resulting rarefaction should satisfy the entropy condition, which is true if $p_l>p$.
Notes
I worked this out using Chapter 14 of Randall Leveque's text on finite volume methods.
There is a 1-parameter family of possible left states (which seems obvious once you check the number of unknowns and constraints).
If you didn't restrict the left-state velocity to be zero, it would be possible to set up a problem where only the shock wave appears by taking the left state to be $(\rho_r^*, u, p)^T$. But since you want zero initial velocities, it's necessary to use the full procedure described above.
