Let me try to answer differently, in some sense more mathematically, and more directly to the point. Intuitively, the dimensionality is the number of independent numbers you need to identify a point. However, the redefinitions of the coordinates need to be continuous which prohibits your "labeling of the pixels"
By the way, one can easily define one-to-one maps from $R^d$ to $R$. For example, the point
$$(0.147346,0.295002,0.139523)$$
may be identified with a single number
$$0.121493759305402623.$$
I have simply taken the digits from all the three coordinates - from 1st; 2nd; 3rd; 1st; 2nd; 3rd, and so on. However, this map from $R^3$ to $R$ is not continuous so one is not allowed to do it when he computes the dimension. In the example above, only the 18 digits behind the decimal point(s) were rearranged but the same thing can clearly be done with the fully precise real numbers, too. In "set theory", an abstract branch of mathematics, they would interpret this construction as a proof that the sets $R$ and $R^3$ have the same cardinality (a generalized number of elements): the set theorists call the number of elements in either set simply "continuum".
In mathematics, the dimensionality - the number of dimensions - is defined by concepts such as Hausdorff dimension:
http://en.wikipedia.org/wiki/Hausdorff_dimension
You try to cover your manifold by a minimum number $N$ of balls of small radius $r$; a notion of a distance has to be available. A ball is a set of point with the distance from the center smaller or equal to $r$. How many balls you need? Well, the volume scales like $r^d$, so you will need $V/r^d$ balls or so. If you take the logarithm of the number of balls, it will be $\ln(V)-d\ln(r)$, and by sending $r\to 0$ i.e. $\ln(r)\to-\infty$, you may extract the coefficient $d$ by a limiting procedure.
Amusingly, this definition also works for fractals that can have fractional dimensions. The simplest ones have dimensionalities that are ratios of logarithms of simple numbers (e.g. integers).
In physics, we use the space to define theories and we differentiate the coordinates and fields with respect to time (and space, in the case of field theory). That's why the condition of "continuity" or "smoothness" is automatically required in physics. In particular, local quantum field theories must live in a spacetime with a well-defined number of spacetime dimensions. Relabeling the coordinates in your "pathological way" doesn't preserve the "differentiable structure" on the spacetime manifold, and because physics depends on derivatives (differentiation), such redefinitions would make physical laws meaningless. Also, quantum field theories are defined on a spacetime that has a well-defined metric tensor; so I can use the Hausdorff definition to count the dimension, too. (One should avoid the "balls" for the Minkowski case which has an indefinite metric.)
All these matters become ill-defined in quantum gravity, however.
In the Hausdorff dimension definition, I needed to consider arbitrarily small balls. But there are no objects smaller than the Planck length - the characteristic (tiny) distance scale of quantum gravity. Consequently, the limiting procedure cannot be performed in quantum gravity. It follows that the number of dimensions of spacetime isn't quite well-defined. Only the dimensions that are "large" - where the balls may still be much smaller than the size of these dimensions - have a physical meaning. However, the number of dimensions that are as small as the Planck length or so (or as curved as the Planck length curvature radius) can't be defined.
And indeed, there are often equivalent descriptions of a theory that actually disagree about the number of dimensions. For example, M-theory on a K3 manifold - which has 11 dimensions in total - is equivalent to heterotic strings on a 3-torus - which only have 10 spacetime dimensions. Also, the AdS/CFT correspondence shows that theories in spacetimes of different dimensions (by one) are equivalent: the radial, "holographic" dimension is invisible in the Lagrangian of CFT which is linked to its significant curvature.