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.