Generators of a finitely generated free module over a commutative ring
If $x_1,\ldots,x_m$ generate $L$, then you get a surjective $A$-module map $A^m\rightarrow L$. Tensoring with $k(\mathfrak{m})=A/\mathfrak{m}$, $\mathfrak{m}$ a maximal ideal, gives you a surjection from an $m$-dimensional $k(\mathfrak{m})$-vector space to an $n$-dimensional $k(\mathfrak{m})$-vector space, so $m\geq n$.
If $n=m$, then you get a surjective endomorphism $L\rightarrow L$, and any surjective endomorphism of a finite $A$-module is injective. So in this case the elements form a basis.
I would like to prove the first assertion without using axiom of choice. Suppose $m < n$. Then $\bigwedge^n L = 0$. This is a contradiction because $\bigwedge^n L$ is a free module of rank $1$.
Your last question can be answered using a nice fact that I learnt from Atiyah - Macdonald. Suppose we have $x_1,\ldots,x_n$ that generate $L \cong A^n$. We now recall the following facts:
Localisation commutes with finite direct sums
If $M,N$ are $A$ - modules then $\phi : M \to N$ is injective iff for all maximal ideals $\mathfrak{m} \in A$ the induced map $\phi_\mathfrak{m} : M_{\mathfrak{m}} \to N_{\mathfrak{m}}$ on localisation is injective.
Using these it is enough to assume that $A$ is a local ring with maximal ideal $\mathfrak{m}$. Now define a map $\phi : A^n \to A^n$ by $\phi(x_i) = e_i$ where $e_i$ are the canonical basis vectors of $A^n$. Then $\phi$ is surjective and we have a ses $$0 \longrightarrow \ker \phi \longrightarrow A^n \stackrel{\phi}{\longrightarrow} A^n \longrightarrow 0$$
which upon tensoring with $A/\mathfrak{m} = k$ gives that $$0 \longrightarrow \ker \phi \otimes_A k \longrightarrow A^n \otimes_A k\stackrel{\phi \otimes 1}{\longrightarrow} A^n\otimes_A k \longrightarrow 0.$$
Rank - nullity implies that $\ker \phi \otimes_A k =0$. But now $\ker \phi \otimes_A k \cong \ker\phi / \mathfrak{m} \ker\phi$ which implies that $\ker \phi = \mathfrak{m}\ker \phi$. We know that $\ker \phi$ is finitely generated and $A$ is local by assumption. The hypotheses of Nakayama's Lemma are now satisfied and applying it shows that $\ker \phi = 0$ and hence $\phi$ is an isomorphism. Hence $x_1,\ldots,x_n$ are a basis for $A^n$.