(I know this an old post, but I hope to provide clarification for any future visitors.)
If I understand the question correctly, I think it would be clearer to write the vector as
\begin{equation}
\vec{A}=A_r\hat r + A_\theta \hat \theta + A_z \hat z.
\end{equation}
A diagram of the unit vectors $\hat{r}$, $\hat{\theta}$, $\hat{z}$ in cylindrical coordinates can be found here.
If the accepted answer (stating that $|\vec{A}|=\sqrt{A_r^2+A_z^2}$ ) were correct, then any vector that points in the $\hat{\theta}$ direction (including $\hat{\theta}$ itself!) would have a norm of $0$, which is absurd.
The key concept here is that the components $A_r$, $A_\theta$, and $A_z$ tell you how much of $\vec{A}$ points in the direction of each unit vector. Since $\hat{r}$, $\hat{\theta}$, and $\hat{z}$ are orthonormal, $|\vec{A}|=\sqrt{A_r^2+A_\theta^2+A_z^2}$ (as the OP correctly guessed).
If you don't believe me, we can derive this result by expressing the cylindrical unit vectors in terms of the Cartesian unit vectors (see the link from above for details):
\begin{align}
\hat{r}&=\cos\theta\,\hat{x}+\sin\theta\,\hat{y}\\
\hat{\theta}&=-\sin\theta\,\hat{x}+\cos\theta\,\hat{y}\\
\hat{z}&=\hat{z}
\end{align}
This allows us to evaluate the norm in the familiar Cartesian coordinate system:
\begin{align}
\left|\vec{A}\right|^2 &= \left| A_u(\cos\theta\,\hat{x}+\sin\theta\,\hat{y})
+A_\theta(-\sin\theta\,\hat{x}+\cos\theta\,\hat{y}) + A_z\hat{z}\right|^2\\
&= \left| (A_u\cos\theta-A_\theta\sin\theta\,)\hat{x}
+(A_u\sin\theta+A_\theta\cos\theta)\hat{y} + A_z\hat{z}\right|^2\\
&= (A_u\cos\theta-A_\theta\sin\theta)^2 + (A_u\sin\theta+A_\theta\cos\theta)^2 + A_z^2\\
&= A_u(\sin^2\theta+\cos^2\theta) + A_\theta(\sin^2\theta+\cos^2\theta) + A_z^2\\
&=A_u^2+A_\theta^2+A_z^2.
\end{align}
Be careful not to confuse all of this with the common practice of using $(r,\theta,z)$ to represent the location of a point in cylindrical coordinates, in which case the distance from the origin is $\sqrt{r^2+z^2}$. But this is different than the question that was asked, since this $\theta$ represents an angle with respect to the positive $x$-axis, not the component of a vector in the $\hat{\theta}$ direction.
Remember that in the analogous case $\nabla \times \nabla f = 0$, some intuition for the result can be attained by integration: by Green's theorem this is equivalent to $\int \nabla f \cdot ds = 0$ around every closed loop, which is true because $\int_{\gamma} \nabla f \cdot ds = f(\gamma(1)) - f(\gamma(0)).$ Thus our intuition is that curl measures circulation, and $\nabla f$ cannot circulate because this would introduce a discontinuity in $f$ around a loop.
Let's try the same thing: by the divergence theorem, it suffices to show that $\int_\Sigma (\nabla \times V) \cdot \hat n\ dA = 0$ for every closed surface $\Sigma$. By Stokes' theorem we know $$\int_\Sigma (\nabla \times V) \cdot \hat n\ dA = \int_{\partial \Sigma}V\cdot ds,$$which vanishes because $\Sigma$ is closed (i.e. $\partial \Sigma = \emptyset$).
In more intuitive terms, the divergence measures flux through a small cube; but the flux of a curl through a closed surface must be zero because there is no boundary curve for the circulation to accumulate upon.
As Nameless alluded to in his comment, you can get a more unified understanding of what's going on here by studying differential forms. All these geometric differential operators $\nabla, \nabla \times, \nabla \cdot$ are exterior derivatives $d_0,d_1,d_2$, and the identity $d_{k+1} \circ d_k = 0$ can be seen either by expanding out the partial derivative expression and noting that everything cancels (what I assume you've done in your proof), but also by applying the general Stokes theorem twice and noting that the boundary of a boundary is always empty.
Best Answer
Obviously, if you have spatially constant vector fields, their spatial rates of change will be 0 in any direction. Application of the divergence and curl produce 0 or the zero vector, respectively. Sort of like how a constant function $f(x)=c$ in single variable calculus has a derivative of 0 everywhere.
Added: Using x,y,z to represent the standard Cartesian basis vectors instead of $\hat{i},\hat{j},\hat{k}$ is a sure recipe for trouble. How do you represent the scalar field $f(x,y,z)=3.5x + 6y + 4z$?
Addendum 2: Note that for coordinate systems in which the basis vectors are a function of space (e.g. cylindrical)
$$ \hat{e}_r = \cos(\theta) \hat{e}_1 + \sin(\theta) \hat{e}_2 \\ \hat{e}_\theta = -sin(\theta) \hat{e}_1 + \cos(\theta) \hat{e}_2 \\ \hat{e}_z = \hat{e}_3 $$
If you have a vector field with (cylindrical) components $5,6,3$ everywhere, it is not really a constant vector field at all because the basis vectors change from point to point
(Notice the contrast with rectangular cartesian, where a vector field with components $5,6, 3$ everywhere is a constant vector field.)
In fact, if you transform the components of this vector back to cartesian, the vector $5,6,3$ has cartesian components which are functions of space. E.g. its x component is $5 \cos(\theta) \hat{e}_1 - 6 \sin(\theta) \hat{e}_2 + \hat{e}_3$, where $\theta=\tan^{-1}(y/x)$