proof of the existence of the Tubular neighborhood In Lee's book, the following reasoning is used to prove the existence of a Tubular neighborhood:
Suppose that $M$ is  an embedded submanifold of $\mathbb R^n$. Then we can define $NM : = \{(x,v)|v \bot T_xM\}$ where orthogonality is defined using the Euclidean metric. To do that we need to identify $T_xM$ with $\mathbb R^n$. Then there is a choice to make. 
How is the whole thing independent of this choice?

As Mosher points out in the comments, asking whether a tubular neighbourhood defined this way is independent of the choice of Riemannian metric doesn't make sense because tubular neighbourhoods are not unique.
Let's suppose you are really asking the following:

What is the right notion of tubular neighbourhood that does not depend on a choice of metric?

One answer is provided by the notion of manifold pairs. 

A manifold pair $(N,M)$ consists of a manifold $M$ and an closed submanifold $N \subset M$.

We can consider "germs" of submanifolds by looking at a certain equivalence relation of manifold pairs:

Two manifold pairs, $(N_i,M_i)$ are equivalent if $N_1 = N_2 = N$ and there is a manifold pair $(N,M)$ such that $M$ is an open subset of both $M_1$ and $M_2$.

Now fix your submanifold $N$ embedded in some larger manifold $W$ and let $M_1$ and $M_2$ be tubular neighbourhoods of $N$ in $W$. Then $M = M_1\cap M_2$ is also a tubular neighbourhood of $N$ in $W$ and we see that the pair $(N,M)$ demonstrates that $(N,M_1)$ and $(N,M_2)$ are equivalent.  
Since any two tubular neighbourhoods of $N$ in $W$ are equivalent as manifold pairs we may conclude that 

As a manifold pair, the equivalence class of a tubular neighbourhood does not depend on a choice of metric. 

I learned about this definition of manifold pairs and their equivalence by reading "symplectic manifolds and their lagrangian submanifolds" by Alan Weinstein.
