One way to do it is through deformation theory, provided we only consider
automorphism groups $G$ of order not divisible by the characteristic (one may of
course assume that it is cyclic of prime order). Then the
the moduli space (or just a miniversal deformation) of all curves of genus $g>1$
is smooth with tangent space at the curve $C$ equal to $H^1(C,T^1_C)$. The
tangent space of the sublocus where the action of $G$ extends is equal to
$H^1(C,T^1_C)^G$ and hence all curves in a neigbourhood of $C$ has an action of
$G$ only when $G$ acts trivially on $H^1(C,T^1_C)$. The (Brauer) character of
the action can be computed by the holomorphic Lefschetz trace formula (resp. of
a lifting of $(C,G))$ and is seen to be non-trivial. (To this I guess one has to add
that there is a finite stratification of the moduli space where the automorphism
group is fixed on each stratum.)
Addendum: In principle this method could also handle automorphisms of order equal to the characteristic (say), what needs to be shown is that they act non-trivially on $H^1(C,T^1_C)$. I haven't thought about that though.
As suggested by Mariano one can also count parameters: Assume $G$ is cyclic of
prime order. If the order is not equal to the characteristic one can use the
Hurwitz formula to get bounds on the genus for the quotient curve and the number
of critical values of the quotient map. Counting parameters for the quotient
curve and the critical values always gives a value which is smaller than $3g-3$
(not a difficult calculation but also not altogether pleasant).
Addendum: The calculation turns out not to be that difficult. Indeed, if we are dealing with an automorphism of prime order $\ell$, if $C\to C'$ is the quotient map and we have $r$ critical values, then the Hurwitz formula gives
3(g-1) = 3\ell(g'-1) + \frac32(\ell-1)r,
where $g'=g(C')$, and on the other hand we want to show (when $g'>1$) that $3(g-1)>3(g'-1)+r$ which follows immediately as $\frac32(\ell-1)>1$. When $g'=1$ we want to show that $3(g-1)>1+r-1=r$ ($1$ parameter for varying the elliptic curve and by automorphisms we may fix one critical value), i.e., $\frac32(\ell-1)r>r$, i.e., $(3\ell-5)r>0$ which is always OK. Finally, with $g'=0$ we are OK if $3(g-1)>\max(r-3,0)$. We may assume $r>3$ and then $r\geq 6$ for reasons of divisibility which easily gives that we are OK unless $r=6$ and $\ell=2$ which gives $g=2$.
The case when
the order is equal to the characteristic is even messier, one has to look at the
local contribution at a critical value to the genus of $C$ which is of
Artin-Schreier type and then bound the number of local parameters in such covers
(we here have parameters even when the critical values and the quotient curve
stay constant). One could also however use the result of Oort saying that a
curve with such an automorphism lifts equivariantly.