This is a community wiki answer compiling the discussion in the comments in order to mark this as answered and remove it from the unanswered queue (once either upvoted or accepted).
Notice that $C=\{x:Ax=b\}$ is an affine space. It is of the form $x_0+\ker A$. It is closed and convex – Federico Nov 19 '18 at 23:16
Since $N$ and $T$ are invariant by translation, meaning $N_{x_0+C}(x_0+x)=N_C(x)$, you just have to study the case of a vector space $\ker A$ – Federico Nov 19 '18 at 23:19
Moreover, since $y+\ker A=\ker A$ if $y\in \ker A$, you can just study what happens at the origin: $N_{\ker A}(0)$ and $T_{\ker A}(0)$. – Federico Nov 19 '18 at 23:21
Going with your hints, doesn't that mean that we obtain $\langle z,c\rangle \leq 0$ for all $c\in \ker(A)$? How would this characterize the normal cone? – ex.nihil Nov 20 '18 at 0:03
Notice that if $c \in \ker A$, then also $−c\in\ker A$. So you get both $\langle z,c\rangle\leq 0$ and $\langle z,−c\rangle \leq 0$. This means that actually $\langle z,c\rangle =0$ ... – Federico Nov 20 '18 at 0:05
So, the vectors normal to $C$ are exactly orthogonal to $C$? Does this mean I can write an explicit form for $N_C(x)$? Pardon my slowness, I have big gaps in my Linear Algebra education which I am trying to compensate. – ex.nihil Nov 20 '18 at 0:11
Indeed, for vector subspaces $V$ you get $N_V=V^\perp$. The normal cone is a generalization of the orthogonal space. The two notions coincide for vector spaces. – Federico Nov 20 '18 at 0:14
And since you said the normal cone is translation-invariant, I presume $N_C=C^\perp$ is also true for affine spaces $C$? – ex.nihil Nov 20 '18 at 0:16
Exactly, with the subtlety that $C^\perp$ is a notation usually reserved for vector subspaces. If $C=x+V$ is an affine space with $V$ its corresponding vector space, you have $N_C=V^\perp$. of course, from this it follows also $T_C=V$. – Federico Nov 20 '18 at 0:18
Best Answer
For $q \in E \setminus C$ define $P(q) = \text{argmin}_{x \in C}\lVert q - x \rVert$. An argmin exists since $C$ is closed, and the argmin is unique since $C$ is convex. It is a basic result that for every $q \in E \setminus C$, $q - P(q) \in N_C(P(q))$. To prove this you can translate coordinates so that $P(q) = 0$, then rotate coordinates so that $q$ is a multiple of $e_n$, and then prove the result by contradiction.
Since $x \in bC = b(E \setminus C)$, there exists a sequence $(q_n)$ in $E \setminus C$ such that $(q_n) \to x$. Set $x_n = P(q_n)$. Since $(q_n) \to x$, we have $\lVert q_n - x_n \rVert = d(q_n, C) \to d(x, C) = 0$. It follows that $(x_n) \to x$ also. Let $v_n = \frac{q_n - x_n}{\lVert q_n - x_n \rVert}$. Note that $v_n \in N_C(x_n)$. Also note that $(v_n)$ is a sequence in the unit sphere, a compact set. Thus passing to a subsequence, we can assume $(v_n) \to v$ for some $v$ in the unit sphere. I leave it to you to show that $v \in N_C(x)$.