My attempt:
I attempted to prove this problem for an example with $V=\mathbb{Q}^3$ which is still not easy. I chose $v = (1,4,-1)$ and $x = (1,1,2)$ and made the following computation: If $B = (v_1,v_2,v_3)$ is some basis over $\mathbb{Q}^3$ with $v_i = (v_{i,1}, v_{i,2}, v_{i,3})$, then
$$(v)_B = x \Leftrightarrow \begin{pmatrix} 1\\ 4 \\ -1 \end{pmatrix} = v_1 + v_2 + 2v_3 = \begin{pmatrix} v_{1,1} & v_{1,2} & v_{1,3} \\ v_{2,1} & v_{2,2} & v_{2,3} \\ v_{3,1} & v_{3,2} & v_{3,3}\end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \\ 2\end{pmatrix}.$$
This looks like we have to do reverse engineering of solving this system of linear equation. To simplify things, I assume the coefficient matrix to be in echelon form, i.e. $v_{2,1} = v_{3,1} = v_{3,2} = 0$. Also, in order to achieve linear independence for $B$, I try to get $v_{i,i} \neq 0$. A solution I found is $v_1 = (1,0,0), \: v_2 = (0,4,0), v_3 = (0,0,-1/2)$.
It looks tedious, and I noticed that this approach will be problematic if one of $x_0$'s coordinate is $0$, i.e. we lose one of the $v_i$'s in our equation. I was not even able to generalize this approach for arbitrary finite-dimensional vector spaces.
Is there a more elegant way to approach this problem? An answer would be nice!
Here is a solution which is quite elementary and does not require any tedious computations:
Let $v_1 := v$ and $w_1 := x$. Since $v_1 \neq 0$ and $w_1 \neq 0$ by assumption, the Basis Extension Theorem states that we can extend the systems $(v_1)$ and $(w_1)$ to bases $B_V = (v_1,\dots,v_n)$ of $V$ and $B_W = (w_1,\dots,w_n)$ of $K^n$.
Since $(w_1,\dots,w_n)$ is a basis, there exists a (unique) linear map $\varphi: K^n \to V$ with $\varphi(w_i) = v_i$ for $i=1,\dots, n$. Moreover, since $B_V$ and $B_W$ are bases, the map $\varphi$ must be an isomorphism.
Let $B = ((\varphi(e_1),\dots, \varphi(e_n))$ where $e_i$ is the $i$-th unit vector of $K^n$. Since $\varphi$ is an isomorphism, the system $B$ is a basis of $V$.
Assume $x = (x_1,\dots,x_n)$. Then we have the equivalence
$$(v)_B = x \: \Longleftrightarrow \: v = x_1 \varphi(e_1) + \dots + x_n \varphi(e_n) = \varphi(x) = \varphi(w_1) = v_1.$$
Sinc the second statement is true due to the construction of $\varphi$, the first statement is also true which we wanted to show.