I don't know how to do this exactly, but one could try a probabilistic approach. Say the representation is $V$, and $V$ is defined over a $\mathbb{C}$ (or at least $\mathbb{Q}$). Pick a random non-zero element $v \in V$ and compute the dimension of the space spanned by the orbit $Gv$. If this dimension is $< \dim V$ then $V$ is reducible and (1) is answered. If not, try again. I would guess that if, after several iterations, the subrepresentations are all equal to $V$, then with high probability $V$ is irreducible. A bad case could be encountered if, e.g., $V$ is a canonical direct sum multiplicity free (but then all your matrices are direct sums, so you wouldn't be asking Edit. This did read "irreducible". As pointed out in the question). If you were worried about this you could conjugate everyone comments by a random element of $GL(V)$.Daniel Litt this is not so!).
The worst part about this algorithm (aside from not detecting reducibility) is having to list the elements of $G$. At least you only need to do But I guess this once is already done according to Alexander's statement of the problem. .. You could also try to approximate the orbit. Say if $\dim V = 1000$ and $G = S_{12}$, then take some random $2000$ elements of $G$ and apply them $v$, and let this be your approximate orbit.
Another bad thing about this algorithm is that it can be numerically unstable.
You could use these ideas to decompose $\mathbb{C}[G]v$ and $V/\mathbb{C}[G]v$ to get an approximation of the irreducible decomposition.
Looking back on my answer, it seems that a lot of things can go wrong. Still, I have applied these ideas in my own work (computing representations that are spanned by $S_n$ or $GL_n$ orbits) and it seems to work well enough to generate conjectures.
