Let $l$ be the field cut out by the action of the Galois group on all the torsion points of $A$, and let $\mathfrak{g} = \operatorname{Gal}(l/k)$. Then $\mathfrak{g}$ is a closed subgroup of $\operatorname{GL}_{2 \operatorname{dim} A}(\widehat{\mathbb{Z}})$.  It is relatively easy to see that $\mathfrak{g}$ is much smaller than the full absolute Galois group of $\mathbb{Q}$ -- for instance, I believe basic group theory shows that there are only finitely many $n$ for which the symmetric group $S_n$ can occur as a quotient of $\mathfrak{g}$ (please let me know if I am wrong or if this turns out to be hard to show).  On the other hand by Hilbert Irreducibility we have for each $n$ a Galois extension $k_n/k$ with Galois group $S_n$.  

Take an affine open subset $A^{\circ}$ of $A$ and by Noether Normalization choose a finite $k$-morphism $\varphi: A^{\circ} \rightarrow \mathbb{A}^n$.  Let $P$ be a point on $\mathbb{A}^n$ whose coordinates generate the field $k_n$, and let $P' \in A^{\circ}(\overline{k})$ be any point with $\varphi(P') = P$.  Then $k(P') \supset k_n$.  So $P'$ does not lie in $A(l)$ and is thus a nontorsion point.  

If $A = E$ is an elliptic curve, you can choose $\varphi$ just to be the $x$-coordinate function, and one should be able to use this argument to construct an explicit nontorsion point on $E(\overline{k})$.

<b>Added</b>: now let $k$ be any field which is *not* algebraic over a finite field.  Then if $A$ is an abelian variety defined over $k$ it is also defined over a subfield $k_0$ which is finitely generated either over $\mathbb{Q}$ or over $\mathbb{F}_p(t)$.  In particular the field $k_0$ is **Hilbertian**, and the above argument goes through to show that $A(\overline{k_0})$ -- and hence also $A(\overline{k})$ -- has nontorsion points.  This is the best possible result, since if $k$ is algebraic over a finite field, $A(\overline{k}) = A(\overline{k})[\operatorname{tors}]$.