Let $V$ be a vector space over a base field $\mathbb F$. Let $V'$ be the dual vector space of all linear functionals $V \to \mathbb F$. If $v_1,\ldots, v_n$ form a basis for $V$, I claim there is a dual basis for $V'$ given by $v_1',\ldots,v_n'$ for which $v_i'\left(v_j\right) = \delta_{ij}$.
This all feels a bit circular.
Let $e_1,\ldots,e_n$ be the standard basis on $V$ and $e_1',\ldots,e_n'$ the standard basis for $V'$, where $e_i'(e_j)=\delta_{ij}$. See how circular this is. I've assumed what I want to show. In coordinates, with $n=3$ then $e_1=(1,0,0)^{\top}$, $e_2 = (0,1,0)^{\top}$ and $e_3=(0,0,1)^{\top}$; general vectors are $x~e_1+y~e_2+z~e_3$, where $x,y,z \in \mathbb F$. In the case of the dual: $e_1' = \mathrm dx$, $e_2' = \mathrm dy$ and $e_3' = \mathrm dz$; general covectors are $p~\mathrm dx + q~\mathrm dy+r~\mathrm dz$, where $p,q,r \in \mathbb F$.
Now I need to use coordinates:
Let a basis for $V$ be $v_1=e_1+e_2-e_3$, $v_2=e_1-e_2+e_3$ and $v_3=-e_1+e_2+e_3$. I seek covectors $v_1',v_2'$ and $v_3'$ for which $v_i'\left(v_j\right) = \delta_{ij}$. Identifying vectors with $3\times 1$ column vectors and covectors with $1\times 3$ row vectors gives
$$\left(\begin{array}{ccc} \leftarrow & v_1' & \rightarrow \\ \leftarrow & v_2' & \rightarrow \\ \leftarrow & v_3' & \rightarrow \end{array}\right)\left(\begin{array}{ccc} 1 & 1 & -1 \\ 1 & -1 & 1 \\ -1 & 1 & 1\end{array}\right) = I_3$$ where $I_3$ is the $3 \times 3$ identity matrix.
Hence:
$$\left(\begin{array}{ccc} \leftarrow & v_1' & \rightarrow \\ \leftarrow & v_2' & \rightarrow \\ \leftarrow & v_3' & \rightarrow \end{array}\right) = \left(\begin{array}{ccc} 1 & 1 & -1 \\ 1 & -1 & 1 \\ -1 & 1 & 1\end{array}\right)^{-1}$$
$$\left(\begin{array}{ccc} \leftarrow & v_1' & \rightarrow \\ \leftarrow & v_2' & \rightarrow \\ \leftarrow & v_3' & \rightarrow \end{array}\right) = \left(\begin{array}{ccc} 1/2 & 1/2 & 0 \\ 1/2 & 0 & 1/2 \\ 0 & 1/2 & 1/2 \end{array}\right)$$
$v_1' = \frac{1}{2}~\mathrm dx+\frac{1}{2}~\mathrm dy$, $v_2'=\frac{1}{2}~\mathrm dx+\frac{1}{2}~\mathrm dz$ and $v_3'=\frac{1}{2}~\mathrm dy+\frac{1}{2}~\mathrm dz$.
I now have a dual basis where $v'_i\left(v_j\right) = \delta_{ij}$.
How do I prove such a basis exists without resorting to coordinates, identifying covectors with rows and vectors with columns, and without inverting coefficient matrices? Is it not circular to assume a basis $e_1,\ldots,e_n$ and $e_1',\ldots,e_n'$ with $e_i'\left(e_j\right)=\delta_{ij}$?
We begin with a basis $v_1,\dots,v_n$ of $V$. We then define a set of linear maps $v_i':V \to \Bbb F$ by $v_i'(v_j) = \delta_{ij}$. Contrary to what you say in the question, there is nothing "circular" about defining linear maps in this way: this is an application of the fact that there is a unique linear extension to any function over a basis (cf. this post for instance). However, there is still the matter of showing that the functionals defined in this way form a basis, i.e. that they are linearly independent and span $V$.
To show that $(v_1',\dots,v_n')$ is a linearly independent sequence, consider any linear combination $f = \lambda_1 v_1' + \cdots + \lambda_n v_n' = 0$. We see that for any $i$, $$ 0 = f(v_i) = \lambda_i. $$ Thus, $\lambda_1 v_1' + \cdots + \lambda_n v_n' = 0$ implies that $\lambda_1 = \cdots = \lambda_n = 0$.
To show that $(v_1',\dots,v_n')$ is a spanning set, consider any $f \in V$. I claim that the linear combination $g = f(v_1)v_1' + \cdots + f(v_n)v_n'$ is equal to $f$. To see that this is the case, show that $f(v_i) = g(v_i)$ for $i = 1,\dots,n$, then once again use the fact that linear functions are uniquely determined by what they do to the elements of a basis.