I am firstly an algebraist and later shifted to probability somehow, so I think I can answer your question from my own experience. I am a algebraist from the bottom of my heart though...A natural thought is you can teach them some basic random matrices, yet you may think it as "linear algebra" so:

**(1) Boolean algebra**

This is the basic building block for axiomatic probability theory and the $\sigma$-algebra is actually a set Boolean algebra. Some advanced in probabilty theory is possible only if you are clear about the structure of Boolean algebra. One example is a post I asked earlier. ([MO post][1]) Interestingly, P.Halmos also wrote both measure theory as well as Boolean algebras. One personal favorite is his "Lectures"

> Halmos, Paul R. "Lectures on Boolean algebras." (1966).

**(2)Stochastic algebra**

This field is relatively young and was proposed mainly by U.Grenander. This algebraic structure is best justified by his comment "...(Kolmogorov)The classical results indicate that such advance should be possible by defining algebraic relations in the space and studying their probabilistic implications. This leads us automatically to think of notions like groups, topological vector spaces and algebras." in the preface(p.13) in

> Grenander, Ulf. Probabilities on algebraic structures. Courier
> Corporation, 2008.

A very readable introduction on this subject of studying probability measure on a algebraic structure is 

> Budzban, Gregory, Philip Joel Feinsilver, and Arunava Mukherjea.
> Probability on Algebraic Structures: AMS Special Session on
> Probability on Algebraic Structures, March 12-13, 1999, Gainesville,
> Florida. Vol. 261. American Mathematical Soc., 2000.

However this is more or less rather analytic-oriented because the basic object the authors had in mind was Lie groups, so I guess this is not what you want. Also mentioned by @Nate Eldredge, some geometric group theory may be what you want if you want to study the group by its representation over random walk space or other kinds of spaces.

**(3)Probabilistic number theory**

From my own knowledge, some number theory problems can be solved using probabilistic method. The most well-known example is the distributions of additive functions defined on algebraic number field in number theory can be described using probabilistic argument. However, as pointed out by [Kublius][2] in Chap X of his famous monograph, such a probabilistic statement is hardly extensible beyond Gaussian number field. As for algebraic number theory I do not know much so no comments.

**(4)Algebraic statistics**

I do not know if you think this is "too combinatorial". But it is a rather popular method to study the Markov random fields(which is a probabilistic subject) on a graph using algebraic approach, see

> Garcia, Luis David, Michael Stillman, and Bernd Sturmfels. "Algebraic geometry of Bayesian networks." Journal of Symbolic Computation 39.3 (2005): 331-355.

There is a whole branch of statistic called "algebraic statistics" which does make use of algebraic geometric notions to proceed, mainly tropical geometry, but that might seem too "combinatorial" to you sometimes.

  [1]: http://mathoverflow.net/questions/217895/about-the-generating-structure-of-borel-field/218005
  [2]: https://www.amazon.com/Probabilistic-Methods-Translations-Mathematical-Monographs/dp/082181561X