There is no really elementary proof, since this is in fact independent of the "constructive" part of the usually axioms of set theory.
However if one has a basic understanding of the axiom of choice then one can easily construct the injection. The axiom of choice says that if we have a family of non-empty sets then we can choose exactly one element from each set in our family.
Suppose that $g\colon Y\to X$ is a surjection then for every $x\in X$ there is some $y\in Y$ such that $g(y)=x$. I.e., the set $\{y\in Y\mid g(y)=x\}$ is non-empty.
Now consider the family $\Bigg\{\{y\in Y\mid g(y)=x\}\ \Bigg|\ x\in X\Bigg\}$, by the above sentence this is a family of non-empty sets, and using the axiom of choice we can choose exactly one element from every set. Let $y_x$ be the chosen element from $\{y\in Y\mid g(y)=x\}$. Let us see that the function $f(x)=y_x$ is injective.
Suppose that $y_x=y_{x'}$, in particular this means that both $y_x$ and $y_{x'}$ belong to the same set $\{y\in Y\mid g(y)=x\}$ and this means that $x=g(y_x)=g(y_{x'})=x'$, as wanted.
Some remarks:
The above proof uses the full power of the axiom of choice, we in fact construct an inverse to the injection $g$. However we are only required to construct an injection from $X$ into $Y$, which need not be an inverse of $g$ -- this is known as The Partition Principle:
If there exists a surjection from $Y$ onto $X$ then there exists an injection from $X$ into $Y$
It is still open whether or not the partition principle implies the axiom of choice, so it might be possible with a bit less than the whole axiom of choice.
However the axiom of choice is definitely needed. Without the axiom of choice it is consistent that there exist two sets $X$ and $Y$ such that $Y$ has both an injection into $X$ and a surjection onto $X$, but there is no injection from $X$ into $Y$.
Being a surjection just means you reach all the elements of your target set, here $A$.
It is quite easy to show it here: take $x\in A$, then $x=f^{-1}(f(x))$, so $x$ is reached by $f^{-1}$. Therefore $f^{-1}$ is surjective.
Best Answer
If $f,g:\mathbb{N}\to \mathbb{N}$ such that for every $n\ge 1$ $f(n)=n+1$ and for every $n\ge 1$ $g(n)=n-1$ if $n>1$ and $g(1)=1$ then $f\circ g=\mathrm{identity}$ ($f$ acts first) but $f,g$ and $g\circ f$ are not bijections.