How variable does a star have to be, to be a variable star? Variable stars are stars whose apparent magnitude varies. But there are so many phenomena that can cause a star to be variable, that I would expect all stars to be variable. A rotating star has a starspot? It's variable! A planet is transiting? It's variable! A cloud of dust passes in front? It's variable! 

This makes me wonder what exactly distinguishes a variable from a non-variable star? Must the variations in brightness be larger than a given magnitude? Must the variations in brightness be periodic? Do dips (or peaks) in brightness be observed more than once?
There is no lower limit, and as you say, all stars are somewhat variable. 

However catalogues of variable stars exist, and they can record a wide range of levels of variability.  For example, the general catalogue of variable stars lists stars like Alpha Triangulum, with a variability of 0.01 magnitudes.

Ultimately a variable star is a star which has had its variability measured and studied and recorded in a catalogue.