Given the axiom of choice, every vector space has a basis (though it will be a very unnatural basis), and you are correct that infinite-dimensional vector spaces are exactly those where the basis is infinite.
But this kind of basis (often called a Hamel basis) is rather useless and impossible to visualize.
So, a more concrete way of thinking about it might be that in an infinite-dimensional vector space, you can exhibit infinitely many vectors $v_1, v_2, v_3, \ldots$ that are all linearly independent; no (finite) linear combination of vectors is zero. Equivalently, $v_n$ is not a linear combination of $v_1, v_2, \ldots, v_{n-1}$ for any $n$.
In particular, this means $\oplus_{i=1}^\infty \mathbb{R}$ (the set of infinite sequences of real numbers where all but finitely many terms are zero) is algebraically a subspace of every infinite-dimensional vector space over $\mathbb{R}$.
How do such vector spaces differ from finite-dimensional vector spaces? Many things break. For example:
Some linear maps do not have any eigenvalues.
Some linear maps are not continuous; you end up having to restrict to Bounded operators which are basically, operators which behave nicely with the norm on your vector space.
The Dual space of the dual space of $V$, $(V^*)^*$, might not equal $V$.
There is a "standard" way to consider normed spaces over arbitrary fields but these are not well-behaved in the case of scalars in finite fields. If you want to work with norms on vector spaces over fields in general, then you have to use the concept of valuation.
Valued field:
Let $K$ be a field with valuation $|\cdot|:K\to\mathbb{R}$. This is, for all $x,y\in K$, $|\cdot|$ satisfies:
- $|x|\geq0$,
- $|x|=0$ iff $x=0$,
- $|x+y|\leq|x|+|y|$,
- $|xy|=|x||y|$.
The set $|K|:=\{|x|:x\in K-\{0\}\}$ is a multiplicative subgroup of $(0,+\infty)$ called the value group of $|\cdot|$. The valuation is called trivial, discrete or dense accordingly as its value group is $\{1\}$, a discrete subset of $(0,+\infty)$ or a dense subset of $(0,+\infty)$. For example, the usual valuations in $\mathbb{R}$ and $\mathbb{C}$ are dense valuations. The valuation is said to be non-Archimedean when it satisfies the strong triangle inequality $|x+y|\leq\max\{|x|,|y|\}$ for all $x,y\in K$. In this case, $(K,|\cdot|)$ is called a non-Archimedean valued field and $|n1_K|\leq1$ for all $n\in\mathbb{Z}$. Common examples of non-Archimedean valuations are the $p$-adic valuations in $\mathbb{Q}$ or the valuations of a field that is not isomorphic to a subfield of $\mathbb{C}$.
Norm: Let $(K,|\cdot|)$ be a valued field and $X$ be a vector space over $(K,|\cdot|)$. A function $p:X\to \mathbb{R}$ is a norm iff for each $a,b\in X$ and each $k\in K$, it satisfies:
- $p(a)\geq0$ and $p(a)=0$ iff $a=0_X$,
- $p(ka)=|k|p(a)$,
- $p(a+b)\leq p(a)+p(b)$
In the case of a finite field, the valuation $|\cdot|$ must be the trivial one.
In fact, if there is nonzero scalar $x\in K$ such that $|x|\neq1$, then $\{|x^n|:n\in\mathbb{Z}\}=\{|x|^n:n\in\mathbb{Z}\}$ is an infinite subset of $K$, which is a contradiction.
Example of Normed space over a finite field: Let $K$ be any field with the trivial valuation (e.g. a finite field) and let $X$ be an
infinite-dimensional vector space with Hamel basis $B$. We can define
a norm $p$ by saying $p(e)$ is the number of nonzero coefficients
there are when we write $e$ as a linear combination of elements of
$B$.
But in this context, we have unexpected situations. For example, two
norms may induce the same topology without being equivalent. In fact,
consider the trivial norm $q$ on $X$ defined by $q(e)=1$ for all
nonzero $e\in X$. Then both norms, $p$ and $q$, induce the discrete
topology, but $p/q$ is unbounded. So there are no constant $C$ such
that $ p\leq Cq$.
A comprehensive starting point to read about normed spaces in this context is the book: Non-Archimedean Functional Analysis - [A.C.M. van Rooij] - Dekker New York (1978).
For more information on finite fields, I recommend the paper: Non-archimedean Banach spaces over trivially valued fields, Borrey, S., P-adic functional analysis, Editorial Universidad de Santiago, Chile, 17 - 31. (1994). There, the norm is assumed to satisfy the strong triangle inequality.
For the study of more advanced stuff, like locally convex spaces over valued fields I recommend the book: Locally Convex Spaces over non-Arquimedean Valued Fields - [C.Perez-Garcia,W.H.Schikhof] - Cambridge Studies in Advanced Mathematics (2010).
Best Answer
You can define a euclidean norm for any basis: take a basis $b = \{b_1, b_2\}$ for $\mathbb{R}^2$ and define $\|\cdot\|_{2,b} : \mathbb{R^2} \to \mathbb{R}$ as:
$$\|x\|_{2,b} = \|\alpha b_1 + \beta b_2\|_{2,b} = \sqrt{\alpha^2 + \beta^2}$$
You can verify that $\|\cdot\|_{2,b}$ is a norm. Indeed, these norms are different for different bases (they are all eqiuvalent, though).
However, for any fixed basis $b$, its definition is basis independent since you can always write a formula for $\|\cdot\|_{2,b}$ using coordinates only:
Let $b = \{(x_1, y_1),(x_2, y_2)\}$ be a basis.
Then we have:
$$(x, y) = -\frac{x_2y+xy_2}{-x_2y_1+x_1y_2}\,(x_1,y_1)+\frac{x_1y-xy_1}{-x_2y_1+x_1y_2}\,(x_2,y_2)$$
So $$\|(x,y)\|_{2,b} = \sqrt{\left(\frac{x_2y+xy_2}{-x_2y_1+x_1y_2}\right)^2 + \left(\frac{x_1y-xy_1}{-x_2y_1+x_1y_2}\right)^2}$$
which is entirely basis independent.