Character free proof that Frobenius kernel is a normal subgroup?

Nothing much to say here. There is (as of now) no proof of this fact without character theory. Although I think there is a direct counting proof when $H$ has even order, and a transfer argument tells you that in a minimal counterexample, $H$ must be perfect (since $H$ is a Hall subgroup of $G$). Hence in a minimal counterexample, $H$ must be a non-trivial perfect group of odd order. There is no such group, but proving that requires a lot more character theory than the proof of Frobenius.

You may also be interested in the following references:

K. Corrádi and E. Horváth, Steps towards an elementary proof of Frobenius’ Theorem, Comm. in Algebra, 24, No. 7 1996, 2285-2292.

Paul Flavell, A Note on Frobenius Groups, Journal of Algebra, 228, 2000, 367-376.

(I hope I didn't screw these up too badly.)

Perhaps it is not too late to elaborate on Geoff answer. For the case when the subgroup $H$ has even order, H. Bender has a character-free proof, actually quite short. Next, when $H$ is solvable, O. Grun has a character-free proof essentially based on a transfer argument (this proof seems to be quite similar to one by R. H. Shaw). Now, by the Feit-Thompson odd-order theorem these two cases exhaust all possibilities for $H$; but alas, the odd-order theorem runs deeper and in its proof there is a lot of character theory!