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.