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.