What techniques are there to prove Schur positivity?

Gasharov's proof that Stanley's chromatic symmetric function is Schur-positive for incomparability graphs of (3+1)-free posets doesn't seem to fit neatly into any of your categories (Discrete Math. 157 (1996), 193–197). He expresses the coefficients of the Schur-function expansion as a signed sum of inner products with complete homogeneous symmetric functions. The summands have a combinatorial interpretation and he defines a sign-reversing involution on them to cancel out everything except certain positive terms. As a byproduct he obtains a combinatorial interpretation of the Schur-function coefficients.

More generally, if you have a combinatorial interpretation of the coefficients when the function is expanded in terms of some other symmetric function basis, then you can try applying the change-of-basis matrix (which in most cases has some kind of combinatorial interpretation, although sometimes it's very complicated), thereby expressing the Schur-function coefficients as some kind of signed sum of combinatorial objects. Then you can look for a sign-reversing involution or some other combinatorial argument to cancel stuff out.

There are also geometric arguments of Schur positivity. The outline is very similar to the representation-theoretic strategy. Construct a variety that deforms into a union of Grassmannians, and show that the cohomology class of the variety gives the polynomial. This often involves finding recursions, and does not give formulas for the coefficients. Examples: Stanley symmetric functions via the Lascoux-Schutzenberger tree, toric Schur functions and $k$-Schur functions.

Note, all I have done is replace "$Sn$-module" with "variety that deforms into a union of Grassmannians" and "Frobenius map of the decomposition into irreducibles" with "cohomology class of the variety" from your representation theoretic outline.