If you only consider a system without the axiom of choice you cannot prove that there is such vector space, simply because while you are not assuming AC -- it might still be true.
However Andreas Blass proved in 1984 that if every vector space has a basis then the axiom of choice holds [1]. In particular it means that if you assume the axiom of choice fails then there is provably a space without a basis.
Semi-constructively, the proof given by Blass uses the equivalence (in ZF) between the axiom of choice the axiom of multiple choice.
The axiom of multiple choice (AMC) asserts that given a family $\cal A$ of non-empty sets, such that every $A\in\cal A$ has at least two elements, then there is a function $F$ such that $F(A)$ is a non-empty, finite, proper subset of $A$ for all $A\in\cal A$.
Blass used this equivalence as follows: given a family of non-empty sets he defines a vector space using this family and by the existence of a basis he constructs $F$ showing that AMC holds.
If we assume the axiom of choice fails, then also AMC fails in this model. Therefore there is a family of sets each containing at least two elements, but there is no $F$ as required. Using this family we can construct the same vector space, but now we can prove that it has no basis. If it had a basis then Blass' proof would follow and a contradiction would be found.
Note that this is semi-constructive since we cannot constructively point out a family of non-empty sets without a choice function, simply because it is consistent that there is none of those. However if we assume that the axiom of choice fails, then we can only infer that such family exists, give it a name and move along. For more see [2].
We can assume "anti-choice" axioms which also tell us particular sets cannot be well-ordered (or families without choice functions), for example we may assume that the real numbers cannot be well-ordered or even a stronger assumption: we can directly assume that the real numbers do not have a basis over $\mathbb Q$. Such assumptions are indeed consistent with ZF, but they are "focused" versions of the negation of the axiom of choice, they tell us a lot about how it fails.
Bibliography:
Andreas Blass, Existence of bases implies the axiom of choice. Contemporary Mathematics vol. 31 pp. 31-33, 1984.
Asaf Karagila, Which set is unwell-orderable? Mathematics StackExchange, Sep. 2012.
Two vector spaces (over the same field) are isomorphic iff they have the same dimension - even if that dimension is infinite.
Actually, in the high-dimensional case it's even simpler: if $V, W$ are infinite-dimensional vector spaces over a field $F$ with $\mathrm{dim}(V), \mathrm{dim}(W)\ge \vert F\vert$, then $V\cong W$ iff $\vert V\vert=\vert W\vert$. In particular, if $F=\mathbb{Q}$, two infinite-dimensional vector spaces over $F$ are isomorphic iff they have the same cardinality.
So, for example:
As vector spaces over $\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{C}$ are isomorphic (this assumes the axiom of choice).
The algebraic numbers $\overline{\mathbb{Q}}$ are not isomorphic to the complex numbers $\mathbb{C}$ as vector spaces over $\mathbb{Q}$, since the former is countable while the latter is uncountable.
EDIT: All of this assumes the axiom of choice - without which, the idea of "dimension" doesn't really make sense. See the comments for a bit more about this.
Best Answer
If $k$ is a field and $V$ is an infinite dimensional $k$-vector space, then $V\cong V\oplus V$. Using this, what you want to show follows from the fact that as $\mathbb Q$-vector spaces, $\mathbb C\cong \mathbb R\oplus \mathbb R$.
Can you see how to prove those two claims?
Later. Ok, apparently not. Let's do it.
(1) If $B$ is a basis for $V$, then the set $$B'=\{(b,0):b\in B\}\cup \{(0,b):b\in B\}$$ is a basis for $V\oplus V$. There is an obvious bijection $B'\cong \{1,2\}\times B$.
Now, if $X$ is an infinite set, then $X$ and $\{1,2\}\times X$ are in bijection. It follows from this that there is a bijection between the basis $B$ of $V$ and the basis $B'$ of $V\oplus V$. As you know, this implies that there is a linear isomorphism between $V$ and $V\oplus V$. This proves my first claim above.
(2) Consider the map $$\phi:a+bi\in\mathbb C\mapsto (a,b)\in\mathbb R\oplus\mathbb R.$$ It is very easy to show that it is an isomorphism of $\mathbb Q$-vector spaces, so that $\mathbb C\cong\mathbb R\oplus\mathbb R$, as my second claim states.
(3) Finally, let's prove your claim that if $\mathbb R$ and $\mathbb C$ are isomorphic $\mathbb Q$-vector spaces: since $\mathbb R$ is a $\mathbb Q$-vector space of infinite dimensions, my first claim tells us that $\mathbb R\cong\mathbb R\oplus\mathbb R$ as $\mathbb Q$-vector spaces. On the other hand, my second claim tells us that $\mathbb R\oplus\mathbb R\cong\mathbb C$ as $\mathbb Q$-vector spaces. Transitivity, then, allows us to conclude that $\mathbb R\cong\mathbb C$ as $\mathbb Q$-vector spaces.