The corollary above is only applicable if $G$ contains an involution, or equivalently, if $G$ is of even order. In fact, any non-abelian finite simple group has even order, so we can start to apply facts about involutions. This is highly non-trivial, and the proof is long and difficult, and is one of the great achievements of 20th century group theory.
Amazingly, there is no proof of this that does not use character theory (although Tao has a proof which is much lighter on the character theory than usual). My impression at the moment is that a necessary condition for removing the character theory from the classification (or related results) is producing a character theory-free proof of Frobenius' theorem (see, for example, this discussion on Tao's blog).
Here I'll present two proofs of Frobenius' theorem in special cases which use no character theory. These prove the theorem when $H$ is either solvable or has even order - by the Feit-Thompson theorem we know this covers all finite groups, but the Feit-Thompson theorem itself is much deeper than Frobenius' theorem!
We have an explicitly defined set $K$, and need to show that it is a normal subgroup. A natural way to proceed is to exhibit $K$ as the kernel of some homomorphism on $G$. Indeed, if we can find a homomorphism $\phi$ on $G$ such that $H\cap \ker \phi=\{1\}$ then this immediately implies that $\ker \phi\subset K$. Furthermore, if $\phi$ is surjective onto a group of size $\lvert H\rvert$, then its kernel has size $\Abs{G}/\Abs{H}=\Abs{K}$, and hence $\ker \phi=K$ and we have proved Frobenius' theorem.
We need to find some homomorphism from $G$ onto a group of size $\Abs{H}$ whose kernel has trivial intersection with $H$. The natural way to fulfil these requirements is that $\phi:G\to H$, and $\phi$ restricted to $H$ is the identity. So now all we need to do is show that the identity homomorphism on $H$ can be extended to a homomorphism on the whole group.
This can be done using the transfer homomorphism...almost. Unfortunately, the transfer homomorphism only works if the image is an abelian group. We therefore need to work with $H/[H,H]$. In general the transfer homomorphism goes from $G$ to $H/[H,H]$, whose restriction to $H$ is the natural quotient map. This means that the kernel is a normal subgroup of $G$ of size $\Abs{K}\Abs{[H,H]}$ which intersects $H$ in $[H,H]$, and hence $\ker \phi$ is the union of $K$ and the conjugates of $[H,H]$. But now we note that $[H,H]$ has the same property in $\ker \phi$ as $H$ did in $G$, and so (provided $[H,H]$ is smaller than $H$) we can proceed by induction.
This has two immediate consequences. The first is that we have proved Frobenius' theorem for solvable groups (by induction on the derived length of $H$, since when $H$ is solvable $[H,H]$ has strictly smaller derived length). The second is that to prove Frobenius' theorem it suffices to prove it when $H$ is a perfect group, i.e. $H=[H,H]$.
It remains to describe what this transfer homomorphism is. We will just describe it in the case when $H$ is abelian - to extend it to the general case of $H/[H,H]$ is a simple quotient construction.
Let $g\in G$. This induces a permutation on the cosets of $H$, where $aH\mapsto ga H$. In particular, if we have some list of transversals of $H$, say $g_1,\ldots,g_k$, then $g$ induces a map on $g_i$, where $gg_i=g_ja_i$ for some $a_i\in H$. We then define \[\phi(g) = a_1\cdots a_k.\] It is a routine calculation to verify that this is indeed a homomorphism, and is independent of the precise choice of transversals. Furthermore, if $H$ is abelian and is a Frobenius complement, then $\phi$ is the identity on $H$. For let $h\in H$, with order $n$. The action $gH\mapsto hgH$ has a single fixed point at $H$, and then orbits of size exactly $n$, since if $h^igH=gH$ then $h^i\in H\cap H^g=\{1\}$. It follows that the $a_1\cdots a_k$ corresponding to $\phi(h)$ is just the identity, since each transversal of the shape $h^ig$ will be mapped to $h^g$, and $\phi(h)$ is the product of elements of the shape $(h^g)^n=1$.
Suppose that there exists an involution $t\in H$. If we consider the $k=\Abs{G}/\Abs{H}-1$ many conjugates of $H$ that are different to $H$, then each must also contain an involution, so we have $k$ many involutions $y_1,\ldots,y_k$ which are not in $H$. If we let $x_i=y_it$, then $x_i^t=ty_i=x_i^{-1}$, and thus we have $k$ many $x\not\in H$ such that $x^t=x^{-1}$.
We claim that these $x$ must all be in $K$. If not, then they must be in some $H^g$, but then $x=h^g$ and $x^t=x^{-1}=(h^{-1})^g$, and so $h=(h^{-1})^{gtg^{-1}}$. Since $h\neq 1$, we must have $gtg^{-1}\in H$, which then forces $g\in H$, and so $x\in H$, which is a contradiction.
Since we have found $k=\Abs{K}-1$ many distinct $x\in K\backslash\{1\}$ such that $x^t=x^{-1}$, this must be true for all elements of $K$! We now argue that there is a unique involution in $H$. Otherwise, if $r\neq t$ are both involutions, then for all $g\in K$ we have $g^{tr}=(g^{-1})^r=g$, and so $(rt)^g=rt$, and hence $rt=1$ and $r=t$. It follows that, since for any $g\in H$ the conjugate $t^g$ is also an involution in $H$, we must have $tg=gt$, that is, $t$ commutes with $H$.
We now show that $K$ is a subgroup. Let $x\neq y\in K$ - we need to show that $xy^{-1}$ is not in any conjugate of $H$, since then it must be in $K$, and we are done. If $xy^{-1}\in H^g$ then $x_1y_1^{-1}\in H$, where $x_1=x^{g^{-1}}$ and $y_1=y^{g^{-1}}$. Therefore we can, without loss of generality, suppose that $xy^{-1}\in H$. If we let $u=xty$ then, since $t$ is central in $H$, \[ (xy^{-1})t = xy^tt=u=t(xy^{-1})=tut=u^t,\] and so $u^t=u$, but this contradicts $u\in H\backslash \{1\}$, and we are done.
[BrFo] R. Brauer and K. A. Fowler, On groups of even order, Ann. of Math. (2) 62 (1955), 565-583.
[FeTh] W. Feit and J. Thompson, Solvability of groups of odd order, Pacific Journal of Mathematics 13 (1963), 775-1029.
[Fr] G. Frobenius, Über auflösbare Gruppen. IV., Berl. Ber. (1901), 1216-1230.
[Is] I. Martin Isaacs, Finite Group Theory, Graduate Studies in Mathematics Volume 92 (2008), American Mathematical Society.