As @cardinal said in a comment:
Actually, after a little thought, I think you algorithm is exactly the Sinkhorn-Knopp algorithm with a very minor modification. Let $X$ be your original matrix and let $Y$ be a matrix of the same size such that $Y_{ij}=X^2_{ij}$. Then, your algorithm is equivalent to applying Sinkhorn-Knopp to $Y$, where at the final step you recover your desired form by taking $\hat{X}_{ij}=sgn(X_{ij})\sqrt{Y_{ij}}$. Sinkhorn-Knopp is guaranteed to converge except in quite pathological circumstances. Reading up on it should be very helpful.
...it seems that the iterative algorithm I suggested in the original question is very similar to the Sinkhorn-Knopp algorithm. Interestingly, it also seems very similar to iterative proportional fitting (IPF), which, as described on the IPF wikipedia page, is related to Newton's method and expectation maximization (all have the same limit).
These iterative methods are often applied to problems which lack a closed form solution, so I will tentatively assume that the answer to the question is negative: there is no way to achieve the desired solution without row/column iteration.
The standard "distance" metric that one typically uses for this type of problem is the Mahalanobis distance.
Assuming that you choose to adopt the Mahalanobis distance as your preferred distance metric, then step 1 that you outlined is indeed correct: normalize all vectors in the training set $V$, plus the new test vector $\overline{v}$, using the L2-norm.
On step 2, your initial description is pretty close, but it's actually slightly more complicated than that. Your idea to calculate the mean vector $\widehat{v}$ over all of the individual normalized vectors in $V$ is correct, however what you need to calculate next is not just the $n$ (or rather, $n+1$, given that you've chosen to index from zero) individual variances, rather, what you actually need is the full $n \times n$ (or $(n+1) \times (n+1)$) covariance matrix. In a MATLAB setting, for example, you'd calculate this using the cov function. The reason why you need the full covariance matrix, and not just the variances (which correspond to the diagonals of the full covariance matrix) is that the variances by themselves don't fully describe the multidimensional shape of $V$'s probability distribution: the random variations among pairs of vector component values may in principle be "correlated"; i.e., an upward statistical fluctuation in the $i$th component of an instance vector $\overline{v}$ could be associated with either an upward fluctuation in the $(i+1)$st component, or a downward fluctuation, or the two might be completely neutral with respect to one another. These potential shape differences are correspondingly encoded by either positive, negative, or zero values for the off-diagonal components of the covariance matrix.
Anyway, once you have the covariance matrix $C$, and the normalized expectation vector $\widehat{v}$, then finally for step 3 you may calculate the Mahalanobis distance of a new test vector $\overline{v}$ using $$d(\overline{v}, \widehat{v}) = \sqrt{(\overline{v} - \widehat{v})^{T} C^{-1} (\overline{v} - \widehat{v})}$$ where $C^{-1}$ represents the matrix inverse of $C$; i.e., $C^{-1}C = I$ (i.e., calculate using inv in MATLAB).
One more point to note: if you have a large number of new vectors $\overline{v}$ whose distance you'd like to calculate, so many instances that collectively they may actually be considered to form their own sample distribution, then as an alternative option you may choose to calculate a net Bhattacharya distance between the two distributions (i.e., the entire training set vs. the entire test set) instead. Of course it really depends on the details of your specific problem context whether or not that would make any sense in this case.
EDIT:
I forgot to mention, there is actually a rather specific reason why Mahalanobis distance is usually a logical choice of distance metric. It's because it appears in the generic expression for the pdf of a multivariate (i.e., vectorized) normal distribution: $$p(\overrightarrow{x}) = \frac{1}{\sqrt{(2 \pi)^{N} \det(C)}} \exp\left[-\frac{\left(\overrightarrow{x}-\overrightarrow{\mu}\right)^{T} C^{-1} \left(\overrightarrow{x}-\overrightarrow{\mu}\right)}{2}\right]$$ In this expression, $\overrightarrow{x}$ represents a multivariate random variable which is normally distributed; it's equivalent to $\overline{v}$ in the above notation, assuming that $\overline{v}$ were normally distributed (often--though not always--the case in real life situations). The value $\overrightarrow{\mu}$ represents the Gaussian mean, equivalent to $\widehat{v}$, while $C$ again represents the covariance, and $N$ gives the number of dimensions or vector components.
The key is to recognize that any set of points $\overrightarrow{x}_{1}, \overrightarrow{x}_{2}, ..., \overrightarrow{x}_{M}$ which all have equal Mahalanobis distances will trace out a contour of equal probability encircling the mode of the pdf. Or, phrased a slightly different way, if I were to give you two random points $(\overrightarrow{x}_{a}, \overrightarrow{x}_{b})$, and then ask you to compare them and tell me which of the two is the further outlier, the Mahalanobis distance is the fundamental underlying concept which permits you to answer that question: by definition, the point with the larger Mahalanobis distance must have a smaller Gaussian probability associated with it, and it is therefore the further of the two outliers.
You should bear in mind, of course, that if your set $V$ of normalized training vectors isn't actually Gaussian, then the above discussion doesn't quite apply precisely; Mahalanobis distance might not be the correct choice of distance metric in that case. But for most practical real life situations, positing variables that are normally distributed often makes a very safe starting assumption.
Best Answer
I think he is asking about feature normalization.
A good discussion already on stats.se: How and why do normalization and feature scaling work?
Also look at Prof. Ng.'s online course: week 2
In case you read Chinese, (I guessed from your username, apologies if you do not.)
read about a good blog post that have some study notes on that part of Prof. Ng.'s lecture.