I think a large group of automorphisms of a curve $C$ only forces 
presence of roots of unity in the endomorphism algebra 
$\text{End}^0(\text{Jac}\ C)$, so this way is likely to produce 
products of abelian varieties with CM by abelian fields. There is a lot
of literature on such examples, e.g. on Fermat curves $x^n+y^n=z^n$, but
they are probably not what you want.

Non-abelian CM seems quite hard to construct explicitly. 
It is easiest to work computationally with curves over ${\mathbb Q}$, 
and usually in genus 1 or 2.
For $g=1$ all CM fields are imaginary quadratic, and for
$g=2$ they are either abelian quartic or have dihedral Galois group $D_8$.
However, there is a theorem of Shimura that says that $D_8$ examples 
do not exist over ${\mathbb Q}$!

To construct such an example over a number field, one can use an approach
of van Wamelen in
<a href="http://www.ams.org/mcom/1999-68-225/S0025-5718-99-01020-0/S0025-5718-99-01020-0.pdf">
`Examples of genus 2 CM curves defined over the rationals'</a>.
This is a very nice paper, where he first shows how to construct such Jacobians 
over ${\mathbb C}$ as lattices (sections 2-3). Then he turns to constructing them as genus 2 hyperelliptic curves over ${\mathbb Q}$, which restricts his examples to abelian Galois groups.
(There is a reference to the aforementioned theorem of Shimura on the last page 
of the paper.) 

One of van Wamelen's examples is carefully worked through in Magma, 
in the chapter on 
<a href="http://magma.maths.usyd.edu.au/magma/handbook/hyperelliptic_curves">
hyperelliptic curves</a>, towards the end in the `From Period Matrix to Curve' 
section. A direct link to it is currently
<a href="http://magma.maths.usyd.edu.au/magma/handbook/text/1402#15470">here</a>
but these tend to change with new releases. 

It can be adapted to construct a $D_8$ example as well, as follows.
Change the field to ${\mathbb Q}(\sqrt{\sqrt{2}-2})$ in that example 
(Galois group $C_4$) by ${\mathbb Q}(\sqrt{2\sqrt{2}-5})$ (Galois group $D_8$).
Then going through that code (plus a little work to get the coefficients as algebraic numbers) gives a hyperelliptic curve with Igusa-Clebsch invariants 
$$
  [36,45(\sqrt{17} + 1)/2,(729\sqrt{17} - 783)/2,-4\sqrt{17} + 36].
$$
The function HyperellipticCurveFromIgusaClebsch then constructs the curve
in the usual form $y^2=$hexic over ${\mathbb Q}(\sqrt{17})$, 
but it has awful coefficients. The example done
in Magma is simplified further using ReducedModel(C: Al:="Wamelen"), but this
function is only implemented over ${\mathbb Q}$. 
The field ${\mathbb Q}(\sqrt{17})$ has class number $1$, and the same 
ReducedModel algorithm would work over this field, I suppose, 
but this is quite a bit of work to implement it properly. 
And, if I am not mistaken, in genus 2 this is possibly one of the simplest
examples.

In any case, if you are happy to have examples as lattices in ${\mathbb C}^g$
rather than equations,
then van Wamelen's paper is a good place to look, I think.