I'll follow Wikipedia's terminology: If $f:V\to W$ is a linear map, then the transpose (or dual) $f^*:W^*\to V^*$ is defined by $$f^*(\varphi)=\varphi\circ f.$$
The first question is: Give an example of a linear map between two vectors spaces such that the transpose is bijective but the original map is neither 1-1 nor onto.
There are no such examples. Indeed, in the above notation, if $f:V\to W$ is not injective, then $f^*:W^*\to V^*$ is not surjective, because the image of $f^*$ consists of those linear forms on $V$ which vanish on $\ker f$. Similarly, if $f$ is not surjective, then $f^*$ is not injective, because the kernel of $f^*$ consists of those linear forms on $W$ which vanish on $f(V)$.
Another question was added in the comments: Are there still no examples if, instead of vector spaces, we consider modules over a commutative ring $R$ with identity?
Such examples exist. A cheap one is given by setting $R=\mathbb Z$, $V=W=\mathbb Z/2\mathbb Z$, $f=0$.
EDIT. In fact we have canonical isomorphisms
(1) $\text{Ker}(f^*)=\text{Coker}(f)^*$ and $\text{Coker}(f^*)=\text{Ker}(f)^*$.
This can bee seen as follows:
(2) If
$$
0\to A\overset{i}{\to}V\overset{f}{\to}W\overset{p}{\to}B\to0
$$
and
$$
0\to A'\overset{i'}{\to}V\overset{f}{\to}W\overset{p'}{\to}B'\to0
$$
are exact sequences of $K$-vector spaces, then there is a unique linear map $a:A\to A'$, and a unique linear map $b:B\to B'$ such that $i'\circ a=i$ and $b\circ p=p'$. Moreover $a$ and $b$ are bijective. The proof is easy.
(3) We have the exact sequences
$$\begin{matrix}
0\to&\text{Ker}(f)&\overset{i}{\to}V\overset{f}{\to}W\overset{p}{\to}&\text{Coker}(f)&\to0,\\ \\
0\to&\text{Coker}(f)^*&\overset{p^*}{\to}W^*\overset{f^*}{\to}V^*\overset{i^*}{\to}&\text{Ker}(f)^*&\to0,\\ \\
0\to&\text{Ker}(f^*)&\to W^*\overset{f^*}{\to}V^*\to&\text{Coker}(f^*)&\to0.
\end{matrix}
$$
Then (1) follows from (2) and (3).
As mentioned in the comment, such a transpose map on $W$ and $V$ is coordinate dependent.
If you want a coordinate independent map, you'll have to stick with the map from $W^*$ to $V^*$.
For a finite dimensional vector space, the double dual space of $V$ (i.e. $V^{**}$) is naturally isomorphic to $V$ (natural here has a technical definition, but essentially means this isomorphism does not depend on coordinates).
On the other hand, even though the dual space of $V$ (i.e. $V^*$) and $V$ are isomorphic, we do not have that they are naturally isomorphic. Picking an isomorphism is nearly the same thing as selecting an inner product (i.e. adding geometry to $V$).
Given a linear map, $A:V \to W$, we can define $A^T:W^* \to V^*$ naturally via $A^T(f)(v)=f(A(v))$. [$f:W \to \mathbb{R}$ is a linear functional on $W$, $A^T(f):V \to \mathbb{R}$ is a linear functional on $V$.]
If we want to define $A^T$ as a map from $W$ to $V$, we'll need to pass (somehow) from $W^*$ to $W$ and $V^*$ to $V$. One way to do this is via inner products.
Suppose that $\langle v_1,v_2 \rangle_V$ is an inner product on $V$ and $\langle w_1,w_2 \rangle_W$ is an inner product on $W$. Then $v \mapsto \langle v, \cdot \rangle_V$ gives an isomorphism from $V$ to $V^*$. Let's give this a name: $\varphi_V(v)=\langle v, \cdot \rangle_V$. Likewise, $w \mapsto \langle w,\cdot \rangle_W$ from $W$ to $W^*$ denoted $\varphi_W(w)=\langle w,\cdot \rangle_W$.
Then we have: $A^T(\varphi_W(w))(v) = (\varphi_W(w))(A(v)) = \langle w, A(v) \rangle_W$. If we then use $\varphi_V^{-1}$ we can turn the linear map $A^T(\varphi_W(w))$ into a vector in $V$. Thus composing maps as follows: $\varphi_V^{-1} \circ A^T \circ \varphi_W$ gives us your desired transpose map:
$$\varphi_V^{-1} \circ A^T \circ \varphi_W:W \to V$$
If we call this $\widetilde{A^T} = \varphi_V^{-1} \circ A^T \circ \varphi_W$, we have
$$ \langle \widetilde{A^T}(w),v \rangle_V = \langle w, A(v) \rangle_W$$
for all $v \in V$ and $w \in W$. Some texts would just use the above equality as the definition of the transpose map (but, of course, this depends on those pesky inner products).
The issue is that turning the transpose map into a map on $W$ and $V$ requires us to pick isomorphisms between $V$ and its dual as well as $W$ and its dual. A special case of this is selecting an inner product.
Picking isomorphisms between vector spaces and their duals is very closely related to selecting bases [Given a basis for $V$, you get a dual basis for $V^*$ and bam you have an isomorphism.]
Likewise, picking an inner product is closely related to selecting a basis [Pick a basis, declare it to be orthonormal, and bam you have an inner product.]
In the end, you really can't get the transpose map to be "coordinate free" on the original vector spaces in the way you're looking for. It all comes down to the fact that a vector space and its dual are not naturally isomorphic.
Best Answer
Let $f: V \to \bar V$ be a linear transformation represented by the matrix $A = [a^i_j]$ relative to the basis $e_1,\dots,e_n$ for $V$ and $\bar e_1, \dots, \bar e_m$ for $\bar V$. Let $\alpha^1, \dots, \alpha^n$ and $\bar \alpha^1, \dots, \bar \alpha^m$ denote the respective corresponding dual bases.
Suppose that $f^*:\bar V^* \to V^*$ satisfies $f^*(\bar \alpha^i) = \sum_{j} b^i_j \alpha^j$. That is, suppose that $[b^i_j]^T$ is the matrix of $f^*$ relative to the dual bases. It follows that for each $i,j$, we have \begin{align*} b^i_j & = \sum_{k} b^i_k \delta^k_j = \sum_{k} b^i_k \alpha^k e_j = \left(\sum_{k} b^i_k \alpha^k\right) e_j = f^*(\bar \alpha^i) e_j = (f^* \circ \bar \alpha^i) e_j \\ & = (\bar \alpha^i \circ f)(e_j) = \bar \alpha^i(f(e_j)) = \bar \alpha^i\left(\sum_{k}a^k_j \bar e_k\right) = \sum_{k}a^k_j \bar \alpha^i \bar e_k = \sum_{k}a^k_j \delta^i_k = a^i_j \end{align*} as desired. That is, the matrix of $f^*$ with respect to the dual bases is $[b^i_j]^T = [a^i_j]^T = A^T$.