Note: This question has been substantially revised, see the edit history for earlier versions.
So far, the only examples of metric spaces which I have seen in topology books are Euclidean $n$-space, subspaces of Euclidean $n$-space, and the discrete space. Obviously, it is not the case that "every metric space of cardinality $\mathfrak c$ is either homeomorphic to a subspace of Euclidean $n$-space or discrete," so I decided to come up with some counterexamples.
I started by sketching what a potential basis set might look like and trying to find a metric to fit it. I made the obvious observation that any metric topologically equivalent to the Euclidean metric on $\Bbb R^2$ generates a basis of open regions bounded by (what I now realize are) Jordan curves. So I tried to think of a metric for which this isn't the case. I noticed that any example I could think of had the property that an open set, the boundary of an open set, or the exterior of an open set would be countable. This leads me to the idea of what I am calling "Jordan spaces" (previously "non-degenerate metric topology"), which I am defining as follows follows:
Let $X$ be a set of cardinality $\mathfrak c$, and $d$ a metric on $X$. The metric space $(X,d)$ is a Jordan space if and only if for every point $x\in X$ and real number $r>0$, the sets $\{y\in X:d(x,y)<r\}$, $\{y\in X:d(x,y)=r\}$, and $\{y\in X:d(x,y)>r\}$
are individually equinumerous with $X$
together form a partition of $X$
(The second criterion is trivial, but important enough to applications that it's worth stating anyway.)
Note that if $d$ is any metric on $\Bbb R^2$ such that the set $\{y\in \Bbb R^2:d(x,y)=r\}$ forms a Jordan curve for any $x\in\Bbb R^2$ and real number $r>0$, then $(\Bbb R^2,d)$ is a Jordan space. This generalizes to $\Bbb R^n$ in the obvious way – in particular, any metric space which is homeomorphic to Euclidean $n$-space is a Jordan space.
Now the question is this: Is every Jordan space homeomorphic to a subspace of Euclidean $n$-space?
My immediate answer is "almost certainly not," and I have some ideas for a proof, but what I would really like is a concrete example.
Additional note: topology is not my native language, please forgive me any mistakes I make and feel free to correct my vocabulary.
Best Answer
A simple way to make sure a space cannot be embedded in any Euclidean space is to ensure it contains copies of $\mathbb R^n$ for arbitarily large n. One example which fits your requirements is the topological sum $\coprod_{n=2}^\infty \mathbb R^n$, with a metric which agrees with the usual one on each individual $\mathbb R^n$. Such a one can be defined as follows. If $x = <x_i> \in \mathbb R^m$ and $y = <y_i> \in \mathbb R^n$ then $$d(x,y) = d_{n+1}(<m,x_1,...,x_m,0,...0>,<n,y_1,...,y_n>)$$ where $d_{n+1}$ is the usual metric on $\mathbb R^{n+1}$. (Intuitively, the $\mathbb R^n$s are embedded in a sequence of parallel hyperplanes in some infinite-dimensional space, each at distance 1 from the next.)
Another example is $\mathbb R^\mathbb N$. The usual proofs that a countable product of metric spaces is metrisable produce a bounded metric, which won't quite fit your requirements; balls over a certain size will have no exterior. But if we keep the usual metric on just the first $\mathbb R$ the proof will still work but give an unbounded metric with the required properties.
A different way to get an example from $\coprod_{n=2}^\infty \mathbb R^n$ is to identify the origins of each component, and use the metric which puts the distance between two points from separate components as the sum of their (Euclidean) distances to their origins. (This does not give the usual quotient topology, that's not metrisable.)
For an example which does not rely on being infinite-dimensional to prevent it being embeddable in a Euclidean space, consider $\mathbb R^3$ with the following metric. $$d(a,b) = \begin{cases} d_3(a,b), & \text{a and b are coplanar with z-axis} \\ min\{d_3(a,c) + d_3(c,b)|\text{c on z-axis}\} & \text{otherwise} \end{cases}$$ (i.e if a and b are not in a common vertical plane, their distance is the length of the shortest path between them that goes through the z-axis.) The open balls around points not on the z-axis are (for sufficiently small radius) 2D Euclidean disks and their boundaries are circles. For points on the z-axis the balls and their boundaries are the same sets as under the Euclidean metric but have completely different topologies. The topology of these balls is homeomorphic to the whole space. Any line in the space which is not coplanar with the z-axis forms a discrete subspace with uncountably many points. So the space is not separable and cannot be embedded in any Euclidean space (or in $\mathbb R^\mathbb N$).