"A gentleman never chooses a basis."
Following up on Qiaochu's query, one way of distinguishing a finite-dimensional $V$ from an infinite one is that there exists a space $W$ together with maps $e: W \otimes V \to k$, $f: k \to V \otimes W$ making the usual triangular equations hold. The data $(W, e, f)$ is uniquely determined up to canonical isomorphism, namely $W$ is canonically isomorphic to the dual of $V$; the $e$ is of course the evaluation pairing. (While it is hard to write down an explicit formula for $f: k \to V \otimes V^*$ without referring to a basis, it is nevertheless independent of basis: is the same map no matter which basis you pick, and thus canonical.) By swapping $V$ and $W$ using the symmetry of the tensor, there are maps $V \otimes W \to k$, $k \to W \otimes V$ which exhibit $V$ as the dual of $W$, hence $V$ is canonically isomorphic to the dual of its dual.
Just to be a tiny bit more explicit, the inverse to the double dual embedding $V \to V^{**}$ would be given by
$$V^{\ast\ast} \to V \otimes V^* \otimes V^{\ast\ast} \to V$$
where the description of the maps uses the data above.
Perhaps it would be most appropriate to answer your question with another question: how do you distinguish a finite-dimensional vector space from an infinite-dimensional one without talking about bases?
At the price of being too categorical for the question, one can follow up Todd's answer as follows. Consider any closed symmetric monoidal category $\mathcal{V}$ with product $\otimes$ and unit object $k$, such as vector spaces over a field $k$. Let $V$ be an object of $\mathcal{V}$ and let $DV = Hom(V,k)$. Just from formal properties of $\mathcal{V}$, there are canonical maps $\iota\colon k\to Hom(V,V)$ and $\nu\colon DV\otimes V\to Hom(V,V)$, which are the usual things for vector spaces. Say that $V$ is dualizable if there is a map $\eta\colon k\to V\otimes DV$ such that $\nu \circ \gamma \circ \eta = \iota$, where $\gamma$ is the commutativity isomorphism. Formal arguments show that $\nu$ is then an isomorphism and if $\epsilon\colon DV\otimes V \to k$ is the evaluation map (there formally), then, with $W=DV$, $\eta$ and $\epsilon$ satisfy the conditions Todd stated for $e$ and $f$. This is general enough that it can't have anything to do with bases. But restricting to vector spaces, we can choose a finite set of elements $f_i\in DV$ and $e_i\in V$ such that $\nu(\sum f_i\otimes e_i) = id$. Then it is formal that $\{e_i\}$ is a basis for $V$ with dual basis $\{f_i\}$. This proves that $V$ is finite dimensional, and the converse is clear as in Todd's answer. There is a result in Cartan-Eilenberg called the dual basis theorem that essentially points out that the precisely analogous characterization holds for finitely generated projective modules over a commutative ring $k$, with the same proof.
Still in a general symmetric monoidal category, if $V$ is dualizable, then a formal argument also shows that the canonical map $V \to V^{**}$ (again defined formally) is an isomorphism. Also, in answer to Peter Samuelson, while the name ``dual basis theorem'' dates from long before my time, it does have some justification. When $\mathcal{V}$ is modules over a commutative ring $k$, if one takes a dualizable $V$ and constructs the free module $F$ on basis $\{d_i\}$ in 1-1 correspondence with the $e_i$ in my previous post, then $\alpha(v) = \sum f_i(v) d_i$ specifies a monomorphism $\alpha\colon V\to F$ such that $\pi\alpha = id$, where $\pi(d_i) = e_i$. This completes the proof that dualizable implies finitely generated projective, with a relevant basis in plain sight.