whats the difference between machine learning and statistics?

There isn't a great deal of difference between the two, and what there is is mostly cultural. Machine Learning came from Computer Science roots whereas Statistics is more mathematical. There's a nice blog post called "Statistics vs. Machine Learning, fight!" by Brendan O'Connor that talks about this.

As for non-statistical approaches to machine learning, well there are several rule-based approaches (decision trees, rule induction, ILP) and there are also approaches like reinforcement learning for control problems. Those don't feel very statistical to me, but you could claim that they are... you could probably claim all of life falls under statistical decision theory if you wanted to (in fact, Marcus Hutter does).

Statistics bases everything on probability models. A typical analysis starts by assuming your data are samples from a random variable with some distribution, then making inferences about the parameters of the distribution.

Machine learning may use probability models, and when it does, it overlaps with statistics. But machine learning isn't so committed to probability. It is willing to also use other approaches to problem solving that are not based on probability.