There are proofs that do not use homology, but I don't know that they are more elementary... For example:

Lemma: If S is an embedded compact surface without boundary in an orientable three manifold M then S is orientable if and only if S separates a regular neighborhood.

Thus if K is an embedded Klein bottle in R^3 then K does not separate R^3. Now we have:

Lemma: If S is an embedded compact surface without boundary in R^3 then S separates R^3 into two pieces, one compact and one not compact.

Proof: Induct on the number of critical points of S with respect to height.//

This is very similar to Alexander's Theorem that spheres in R^3 separate.

There are proofs that do not use homology, but I don't know that they are more elementary... For example:

Lemma: If S is an embedded compact surface without boundary in an orientable three manifold M then S is orientable if and only if S separates a regular neighborhood.

Thus if K is an embedded Klein bottle in R^3 then K does not separate R^3. Now we have:

Lemma: If S is an embedded compact surface without boundary in R^3 then S separates R^3 into two pieces, one compact and one not compact.

Proof: A cut and paste argument, inducting on the number of saddle points of S with respect to height.//

This is very similar to Alexander's Theorem that spheres in R^3 separate.