As a physicist, I would say the most obvious example is $n$-dimensional Euclidean space, with $n > 1$. Since a few people have mentioned casually that Euclidean spaces do have natural bases, I should explain myself...
Informally, a Euclidean space is supposed to be an idealization of something like a giant sheet of paper with an origin marked in pencil, or interstellar space with an origin marked by a certain star. If you're in the habit of carrying around a tape measure, a space like this has a natural metric, and you can turn it into a vector space in the obvious way (using the metric to define scalar multiplication and the parallelogram rule to define addition).
From this point of view, Euclidean space clearly has no natural basis, because if you're stranded on a giant sheet of paper, or floating in interstellar space, there's no natural set of "special" directions.
Unfortunately, I don't know offhand how to formalize this argument. My guess is that you would start with Hilbert's axioms for Euclidean $n$-space, and choose an arbitrary point to be the origin. Hartshorne mentions in Geometry: Euclid and Beyond that in Hilbert's framework, the congruence classes of line segments naturally become the positive elements of an ordered field, which is of course isomorphic to $\mathbb{R}$. Choosing an arbitrary congruence class of line segments to be the "unit segments," you get a metric on your space. You can then turn the set of points into a vector space, using the metric to define scalar multiplication and the parallelogram rule to define addition (just like before, but now rigorously). It seems obvious to me that this vector space will have no natural basis.