As has been noted the number $N$ of vectors needs to be at least $2n$. Also the list $V=(v_1,\ldots,v_N)$ needs to contain a basis of $\mathbb{R}^n$, otherwise the matrix $V$ has rank less than $n$ and thus 
$$ \begin{pmatrix} V \\ VA \end{pmatrix}$$
has rank less than $2n$. Without loss of generality we may assume that the first $n$ of the list are linearly independent. Let's partition $V= (V_1,V_2)$ accordingly and do the same for the diagonal matrix. We are then looking at
$$ \begin{pmatrix} V \\ VA \end{pmatrix}=\begin{pmatrix} V_1 & V_2 \\ V_1A_1 & V_2 A_2 \end{pmatrix}.$$
As $V_1$ is invertible we may eliminate the block $V_2$ without changing the rank. I.e. 
$$ \begin{pmatrix} V_1 & V_2 \\ V_1A_1 & V_2 A_2 \end{pmatrix}\begin{pmatrix} I_n & -V_1^{-1}V_2 \\ 0 & I_{N-m} \end{pmatrix}=\begin{pmatrix} V_1 & 0 \\ V_1A_1 & V_2 A_2 - V_1 A_1 V_1^{-1}V_2\end{pmatrix}.$$
The question is thus whether $V_2 A_2 - V_1 A_1 V_1^{-1}V_2$ has full rank, or equivalently whether 
$$ V_1^{-1}V_2 A_2 -  A_1 V_1^{-1}V_2 $$
has full rank. This looks like a [Sylvester equation](https://en.wikipedia.org/wiki/Sylvester_equation) in $X=V_1^{-1}V_2$. So for instance, if $V_2$ is also $n$-dimensional and the diagonal elements of $A_1$ and $A_2$ are distinct, you can take any invertible matrix $C$ and there exists a unique $X$ such that
$$ X A_2 - A_1 X = C.$$
Then choose any invertible $V_1$ and let $V_2 = V_1 X$.