There are several ways of describing this result:
Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor).
I tend to think of it as:
Theorem: For, $k \in \{0,1,\ldots,n-1\}$, any $k \times n$ Latin rectangle extends to a $(k+1) \times n$ Latin rectangle.
The only proof I've seen is via Hall's Marriage Theorem.
Q: Can this result be proved without the use of Hall's Marriage Theorem?
I.e., can it be proved without something the amounts to the use of something equivalent to Hall's Marriage Theorem in some essential way (e.g. replacing "by Hall's Marriage Theorem" by a proof of Hall's Marriage Theorem).
That a $k$-regular bipartite graph has a perfect matching (even a $1$-factorization) follows immediately from the following:
where as usual $\chi^\prime(G)$ is the edge chromatic number and $\Delta(G)$ is the maximum degree.
Proof: Keep properly coloring the edges of $G$ with colors $\{1,2,\ldots,\Delta(G)\}$ as long as possible. Suppose that an edge $uv$ can not be properly colored. We modify the existing coloring to allow us to color $uv$ as follows.
Let $C(u)$ be the colors that are used on edges incident with $u$ and similarly define $C(v)$. Of course $|C(u)|<\Delta(G)$ and $|C(v)|<\Delta(G)$. On the other hand, as there is no color available to properly color $uv$ we have $C(u)\cup C(v)=\{1,2,\ldots,\Delta(G)\}$. The above two sentences imply that there is a color $i\in C(u)\setminus C(v)$ and a color $j\in C(v)\setminus C(u)$.
Well, consider the longest path $P$ starting at $u$ with edges alternating between colors $i$ and $j$. Note that $v\not\in P$ as otherwise $P\cup uv$ would form a cycle of odd length. Hence we can now simply exchange colors $i$ and $j$ along this path, and then color $uv$ with color $i$.