Finding a basis of an infinite dimensional vector space with a given vector

Yes (as long as $v \neq 0$). You prove that a basis exists via Zorn's Lemma, proving that a maximal element (which must exist by Zorn's Lemma) in the collection of linearly independent subsets of $V$ (partially ordered by inclusion) is a basis. This proof shows that any linearly independent set can be extended to a basis -- just take a maximal element that extends the linearly independent set. But the proof necessarily uses the Axiom of Choice so it won't be constructive.

Let $A$ be a basis of $V$ (using AC) and $v \in V$. Then $v$ is a finite linear combination of elements of $A$. wlog assume that combination is $$ v = a + k_2a_2 + \cdots + k_na_n . $$

Then $B = A/\{a\} \cup \{v\}$ is a basis: it spans, and any finite subset is linearly independent.