Transformations law for tensor: why $\partial_{\mu} A^{\nu}$ is not a well defined tensor ? Where is my mistake. I totally reformulate my question to express precisely my problem. I reason on tensor $(1,1)$ for simplicity even if what I say could be more general.
A quantity $T^{\nu}_{\mu}$ i said to be a tensor if under a change of variable $x \rightarrow \widetilde{x}$, it follows the property:
$$T^{\nu}_{\mu}=\frac{\partial \widetilde{x}^{\alpha} }{\partial x^{\mu}} \frac{\partial x^{\nu}}{\partial \widetilde{x}^{\beta} }  \widetilde{T}^{\beta}_{\alpha}$$
Consider the quantity $T_{\mu}^{\nu}=\partial_{\mu} A^{\nu}$
I know that we usually say it is not a tensor and I understand the reason we associate to it. If I consider a change of frame $x \rightarrow \widetilde{x}$, then I have:
$$\partial_{\mu} A^{\nu}=\frac{\partial \widetilde{x}^{\alpha} }{\partial x^{\mu}}\widetilde{\partial}_{\alpha} \left( \frac{\partial x^{\nu}}{\partial \widetilde{x}^{\beta} } \widetilde{A}^{\beta} \right)$$
$$\partial_{\mu} A^{\nu}=\frac{\partial \widetilde{x}^{\alpha} }{\partial x^{\mu}} \frac{\partial x^{\nu}}{\partial \widetilde{x}^{\beta} } \widetilde{\partial}_{\alpha} \widetilde{A}^{\beta} + \frac{\partial \widetilde{x}^{\alpha} }{\partial x^{\mu}} \frac{\partial^2 x^{\nu}}{\partial \widetilde{x}^{\alpha} \partial \widetilde{x}^{\beta} } \widetilde{A}^{\beta}$$
Because of this extra second derivative term, it doesn't follow the property I am asking. Then it cannot be a tensor. I think I understand this approach.
Here, I emphasize that the reason it is not a tensor is because we implicitly define $\widetilde{T}^{\beta}_{\alpha}$ as being $T^{\nu}_{\mu}$ where we replaced all vector and covector components appearing by the corresponding components in $\widetilde{x}$. I.e, what we expect to call $\widetilde{T}^{\beta}_{\alpha}$ would be $\widetilde{T}^{\beta}_{\alpha}=\widetilde{\partial}_{\alpha} \widetilde{A}^{\beta}$. I go back to it in the next part.

Now consider the following:
I choose a particular frame $x$ in which I say $T^{\nu}_{\mu}=\partial_{\mu} A^{\nu}$.
Then, I define the quantity $\widetilde{T}^{\beta}_{\alpha}=\frac{\partial \widetilde{x}^{\beta} }{\partial x^{\nu}} \frac{\partial x^{\mu}}{\partial \widetilde{x}^{\alpha} } T^{\nu}_{\mu}$
Thus, here we have $\widetilde{T}^{\beta}_{\alpha} \neq \widetilde{\partial}_{\alpha} \widetilde{A}^{\beta} $. The interpretation of $\widetilde{T}^{\beta}_{\alpha}$ is then different from what we wanted to have in the previous part: it has only the interpretation of derivative of a vector component in the initial frame $x$. It loses this interpretation in $\widetilde{x}$.
Why cannot I say that this quantity is a tensor ? 
It follows the good law of transformation and it is well defined.
Indeed, consider any vector $a$ and covector $b$, if I compute $T(a,b)$ in the frame $x$ it gives me:
$$T(a,b)=\left( \partial_{\mu} A^{\nu} \right) a^{\mu} b_{\nu}$$
In the frame $\widetilde{x}$ it gives me:
$$T(a,b)=\left( \partial_{\mu} A^{\nu} \right) \frac{\partial \widetilde{x}^{\beta} }{\partial x^{\nu}} \frac{\partial x^{\mu}}{\partial \widetilde{x}^{\alpha} } \widetilde{a}^{\alpha} \widetilde{b}_{\beta}=\left( \partial_{\mu} A^{\nu} \right) a^{\mu} b_{\nu}$$
Thus the map $T$ is well defined (the map doesn't depend on the frame I use to describe it, it exists indepentantly of any frame).

My questions: 
Various answer tell me that my way of definining the tensor is ill-defined (I guess in the sense my map cannot exist) ? Why ? For me it works I don't see any contradiction.
If there is indeed no contradiction, why isn't this way used to define a "valid" tensor $\partial_{\mu} A^{\nu}$. Is it for aesthetical reasons or there are good mathematical reasons that says that this quantity would be bad and would'nt represent the variation of a vector field ?
 A: Your approach is completely fine, and it is subsumed into covariant derivatives. One thing that makes your approach less general is that it takes one particular coordinate system as special, and assumes that the Christoffel symbols vanish in that system (and hence in particular the resulting affine connection is flat). You will have trouble if, for example, your manifold cannot be covered by a single coordinate chart. The advantage of the Christoffel symbols is that you don't have any issues with nontrivial topologies, and you will be able to talk about non-flat affine connections.
Let us see how we can "hide" the special coordinate system and discover that the Christoffel symbols were lurking beneath this. In your notation, we can write the components of $T$ in the $\tilde x$-coordinates as
$$
\tilde T^\beta_\alpha=\tilde{\partial}_{\alpha} \tilde{A}^{\beta} + \frac{\partial \tilde{x}^{\beta} }{\partial x^{\nu}} \frac{\partial^2 x^{\nu}}{\partial \tilde{x}^{\alpha} \partial \tilde{x}^{\gamma} } \tilde{A}^{\beta},
$$
that is,
$$
\tilde T^\beta_\alpha=\tilde{\partial}_{\alpha} \tilde{A}^{\beta} + \tilde\Gamma^\beta_{\alpha\gamma} \tilde{A}^{\beta},
\qquad\textrm{where}\qquad
\tilde\Gamma^\beta_{\alpha\gamma} = \frac{\partial \tilde{x}^{\beta} }{\partial x^{\nu}} \frac{\partial^2 x^{\nu}}{\partial \tilde{x}^{\alpha} \partial \tilde{x}^{\gamma} }.
$$
In a new coordinate system we call $\bar x$, we would obviously have
$$
\bar T^\beta_\alpha=\bar{\partial}_{\alpha} \bar{A}^{\beta} + \bar\Gamma^\beta_{\alpha\gamma} \bar{A}^{\beta},
\qquad\textrm{where}\qquad
\bar\Gamma^\beta_{\alpha\gamma} = \frac{\partial \bar{x}^{\beta} }{\partial x^{\nu}} \frac{\partial^2 x^{\nu}}{\partial \bar{x}^{\alpha} \partial \bar{x}^{\gamma} }.
$$
It is not difficult to derive the following transformation law for the $\Gamma$-coefficients:
$$
\bar\Gamma^\beta_{\alpha\gamma} = \tilde\Gamma^\lambda_{\mu\nu} 
\frac{\partial \bar{x}^{\beta} }{\partial \tilde{x}^{\lambda}}
\frac{\partial \tilde{x}^{\mu} }{\partial \bar{x}^{\alpha}}
\frac{\partial \tilde{x}^{\nu} }{\partial \bar{x}^{\beta}}
+\frac{\partial \bar{x}^{\beta} }{\partial \tilde{x}^{\nu}} \frac{\partial^2 \tilde{x}^{\nu}}{\partial \bar{x}^{\alpha} \partial \bar{x}^{\gamma} } .
$$
Thus, once the $\Gamma$-coefficients are known in some coordinate system, its values can be computed in any other coordinate system. We never need to refer to the original "special" $x$-coordinate system. These $\Gamma$-coefficients are actually called the Christoffel symbols.
A: A set of $n^{p+q}$ quantities $T^{h_1, ...h_p}_{k_1,...k_q}$ is said to constitute the components of a
tensor of type $(p,q)$ at a point P of a differentiable manifold $X_n$ if, under a coordinate transformation $T^{h_1, ...h_p}_{k_1,...k_q}$ transform according to the law
\begin{equation}
T^{i_1, ...i_p}_{j_1,...j_q}=\frac{\partial \widetilde{x}^{i_1}}{\partial x^{h_1}}...\frac{\partial \widetilde{x}^{i_p}}{\partial x^{h_p}} \frac{\partial x^{k_1}}{\partial \widetilde{x}^{j_1}}...\frac{\partial x^{k_q}}{\partial \widetilde{x}^{j_q}} T^{h_1, ...h_p}_{k_1,...k_q}
\end{equation}
A special case of the definition above is thet of contravariant vectors of type (1,0), whose transformation low is
\begin{equation}
\widetilde{A}^{\alpha}=\frac{\partial \widetilde{x}^{\alpha}}{\partial x^{\mu}} A^{\mu}
\end{equation}
As pointed out by levap the quantity $\partial_{\mu} A^{\nu}$ is the partial derivatives of the components of the vector A with respect to some basis. There is a major difference when differentiation a scalar field $\phi(x^k)$ and a contravariant vector field $A^{h}(x^k)$. When considering the scalar field, we pass from a point P with coordinates $x^k$ to a neighboring point Q with coordinates $x^k+dx^k$, the differential is given by
\begin{equation}
d\phi=\frac{\partial \phi(x^k)}{\partial x^k} dx^k
\end{equation}
The components $\frac{\partial \phi(x^k)}{\partial x^k}$ of $d\phi$ are a covariant vector, $dx^k$ are the component of a contravariant vector, so the inner product $d\phi$ is a scalar quantity. The situation is quite different when considering the contravariant vector field $A^{h}(x^k)$. When moving from a point P with coordinates $x^k$ to a neighboring point Q with coordinates $x^k+dx^k$, the differential $dA^{h}$ is:
\begin{equation}
dA^{h}=\frac{\partial A^{h}}{\partial x^k} dx^k
\end{equation}
These differentials would represent the components of a contravariant vector if the partial derivatives $\frac{\partial A^{h}}{\partial x^k}$ were the components of a type (1,1) tensor, but this is not necessarely the case. In order to understand why we can have a look to the transformation low of the contravariant vector field $A^{h}(x^k)$ when changing the basis:
\begin{equation}
 \widetilde{A}^{j}( \widetilde{x}^p)=\frac{\partial  \widetilde{x}^{j}}{\partial x^h} dA^h(x^q)
\end{equation}
when differentiation with respect to $\widetilde{x}^k$ by using the chain rule we can write:
\begin{equation}
\frac{\partial \widetilde{A}^{j}( \widetilde{x}^p)}{\partial \widetilde{x}^{k}}=\frac{\partial^2 \widetilde{x}^{j}}{\partial x^l \partial x^h} \frac{\partial x^l}{\partial \widetilde{x}^{k}} A^h+ \frac{\partial  \widetilde{x}^{j}}{\partial x^h} \frac{\partial x^l}{\partial \widetilde{x}^{k}} \frac{\partial A^h}{\partial x^l}
\end{equation}
When considering the relation above we can conclude that $\frac{\partial A^h}{\partial x^l}$ are not the components  of a tensor. However if the first term in the above relation is zero, thus in the case of affine vecto field $A^j(x^h)$ the partial derivative represents the component of a (1,1) tensor. This happens when
\begin{equation}
\frac{\partial^2 \widetilde{x}^{j}}{\partial x^l \partial x^h}=0
\end{equation}
i.e. when we are dealing with the coordinate transformation is linear. No if we multiply $\frac{\partial \widetilde{A}^{j}( \widetilde{x}^p)}{\partial \widetilde{x}^{k}}$ by $d\widetilde{x}^k$ and we sum over $k$ we get:
\begin{equation}
\frac{\partial \widetilde{A}^{j}( \widetilde{x}^p)}{\partial \widetilde{x}^{k}} d\widetilde{x}^k=\frac{\partial^2 \widetilde{x}^{j}}{\partial x^l \partial x^h} A^h dx^l + \frac{\partial  \widetilde{x}^{j}}{\partial x^h} \frac{\partial A^h}{\partial x^l} dx^l
\end{equation}
Now using the expression for the differential$dA^{h}$ above we have:
\begin{equation}
d\widetilde{A}^j=\frac{\partial^2 \widetilde{x}^{j}}{\partial x^k \partial x^h} A^h dx^k + \frac{\partial  \widetilde{x}^{j}}{\partial x^h} dA^h
\end{equation}
This is the transformation law of the differentials of the contravariant vector field $A^h(x^k)$. Once more these differentials are not the components of a tensor. The transformation law refers to the components of the Tensor. This is because by definition of tensor the transformation law is always linear in the components of the tensors. This allows us to define the multiplication by a scalar as well as the addition of tensors of equal rank. Because of this operation, it is possible to regard all  tensors of a given rank as elements of a vector space.
A: 
This question always confused me when talking about tensor: how they should behave under change of variable.

Actually, one could argue that how tensors transform under general coordinate transformations is what you've understood best here. The blue equation below defines tensors of any signature, but you've written down the correct equations for tensors with $1$ index, including the "ordinary" vector $v^\nu$, the infinitesimal vector $dx^\mu$, and the partial derivative $\partial_\nu$. By "ordinary" I mean they aren't operators; $\partial_\mu$ is instead a vector operator.

From the way the basis vector transform I deduce the way the
  coefficient transform:
$$\widetilde{A}^{\alpha}= \frac{\partial\widetilde{x}^{\alpha}}{\partial x^{\mu}} A^{\mu}$$
Great, it shouldn't be more complicated with arbitrary tensors right ?

The calculations you did in this example are fine, but you have the reasoning backwards. We don't deduce how a vector field transforms from the requirement that $A^\mu\partial_\mu$ is invariant, i.e. is a scalar. We deduce that the contraction - done right; see the longer of two comments below on contraction - of two vectors (i.e. rank-$1$ tensors) is a scalar (i.e. rank-$0$ tensor) from the definition of a tensor. Explicitly, a $(p,\,q)$-signature tensor $T$ obeys$$\color{blue}{T^{\bar{\alpha}_1\cdots\bar{\alpha}_p}_{\quad\qquad\bar{\beta}_1\cdots\bar{\beta}_q}=\frac{\partial x^{\bar{\alpha}_1}}{\partial x^{\mu_1}}\cdots\frac{\partial x^{\bar{\alpha}_p}}{\partial x^{\mu_p}}\frac{\partial x^{\nu_1}}{\partial x^{\bar{\beta}_1}}\cdots\frac{\partial x^{\nu_q}}{\partial x^{\bar{\beta}_q}}T^{\mu_1\cdots\mu_p}_{\quad\qquad\nu_1\cdots\nu_q}}.$$
I need to talk also about how contraction works. 
The shorter of two comments about contraction
When I count indices on a quantity, I don't count contracted pairs. For example, $w_\mu v^\mu$ has $0$ indices, not $2$. The way a tensor transforms depends only on its uncontracted indices, so bear that in mind when double-checking everything with the blue equation above.
The longer one, ending with a horizontal line
Operators such as $\partial_\mu$ are really ways to transform "ordinary" objects; they're "higher-order" objects in that sense. For example, if $\phi$ is a scalar, you can use the above definition to prove that $\partial_\mu\phi$ is a vector and $v^\mu\partial_\mu\phi$ is a scalar. So $v^\mu\partial_\mu$ maps scalars to scalars, and is a scalar operator. By the same logic, $v^\mu\phi$ is a vector. But what is$$\partial_\mu(v^\mu\phi)?$$Don't let its lack of indices fall you: that just tells you it won't transform as any of the infinitely many kinds of tensor that aren't scalars. But the scalar-to-scalar operator that has transformed $\phi$ in this second example - let's call it $L$ - satisfies $L\phi=\color{limegreen}{v^\mu\partial_\mu\phi}+\color{red}{(\partial_\mu v^\mu)\phi}$ and can be written as$$L=\color{limegreen}{v^\mu\partial_\mu}+\color{red}{(\partial_\mu v^\mu)}.$$We already showed the green part's a scalar-to-scalar operator, but the red part is a very different beast. Indeed,$$\partial_\mu v^\mu=\partial_\mu\left(\frac{\partial x^\mu}{\partial\bar{x}^\bar{\alpha}}v^\bar{\alpha}\right)=\color{limegreen}{\frac{\partial x^\mu}{\partial\bar{x}^\bar{\alpha}}\partial_\mu v^\bar{\alpha}}+\color{red}{\left[\partial_\mu\left(\frac{\partial x^\mu}{\partial\bar{x}^\bar{\alpha}}\right)\right]v^\bar{\alpha}}.$$The green part can be simplified to $\partial_\bar{\alpha}v^\bar{\alpha}$, so looks like what we started with. But because of the bonus red term, the original expression isn't transforming as a tensor. 

These examples have shown that the lack of spacetime indices doesn't make a quantity the kind of tensor that lacks such indices. Your original question is about why a quantity having two indices doesn't have to be the kind of tensor that has two. So let's get to that:

Indeed, this would simply be a particular case of my general reasoning with $T_{\mu}^{\nu}$.

But as the $0$-indexed example shows, your general reasoning doesn't work. We don't start by assuming all such quantities are invariant, and then pull out factors in which not all indices are contracted as coefficients. We start from the defining equation for tensors, and see what qualifies and what doesn't.

I would expect to have$$\widetilde{\partial}_{\alpha} \widetilde{v}^{\beta}=\partial_{\mu}v^{\nu} \frac{\partial x^{\mu}}{\partial \widetilde{x}^{\alpha} }\frac{\partial \widetilde{x}^{\beta}}{\partial x^{\nu} }$$

The $0$-indices example above already showed what the problem is. $\partial_\mu v^\mu$ didn't work the same way as $v^\mu\partial_\mu$, because of a second term from the product rule for derivatives. Treating $v^\mu$ as the operator that multiplies an arbitrary quantity by $v^\mu$, that operator doesn't commute with the $\partial_\mu$ operator. You have to be very careful with the arithmetic of non-commuting operators. (On the other hand, $v^\mu$ commutes with $v^\nu$, while $\partial_\mu$ commutes with $\partial_\nu$.) So the correct calculation is
$$\partial_\bar{\alpha}v^\bar{\beta}=\frac{\partial x^\mu}{\partial\bar{x}^\bar{\alpha}}\partial_\mu\left(\frac{\partial\bar{x}^\bar{\beta}}{\partial x^\nu}v^\nu\right)=\color{limegreen}{\frac{\partial x^\mu}{\partial\bar{x}^\bar{\alpha}}\frac{\partial\bar{x}^\bar{\beta}}{\partial x^\nu}\partial_\mu v^\nu}+\color{red}{\left[\frac{\partial x^\mu}{\partial\bar{x}^\bar{\alpha}}\partial_\mu\left(\frac{\partial\bar{x}^\bar{\beta}}{\partial x^\nu}\right)\right]v^\nu}$$Again, the green part is all you'd get if we were transforming a tensor, but the red part proves we aren't. This $2$-indices case generalises what we did before, as that was just contracted out the surviving indices here. All your calculations, regardless of method, have the same pair of problems:


*

*You guess that a lack of indices implies a scalar, but it doesn't;

*You neglect the failure of partial derivatives to commute with other operators.


But you're right when you write a vector of any kind as a partial-derivative factor contracted with that vector in another coordinate system. The problem is that when this vector is in the argument of a derivative, this factor's own derivative adds a term that contradicts the definition of a tensor.
In differential geometry, we have upgrades to the usual partial derivative called "connections" that really do map tensors to tensors. So $\nabla_\mu v^\nu$ is a rank-$2$ tensor, $\nabla_\mu v^\mu$ is a scalar etc. Wikipedia gets awfully technical when discussing the topic, but this is probably the easiest entry point they offer if you want to learn how it works.
Update
Your rewrite obtains the tensor $\nabla_\mu A^\nu$, but you probably already know that thanks to @timur's answer. Actually, your rewrite plus that answer could be a valuable way to teach connections. Unfortunately, the specific connection that results isn't the ever-popular Riemannian connection, the unique metric-preserving torsion-free affine connection. In particular, your connection isn't metric-preserving:$$\begin{align}T_{\bar{\alpha}}^{\bar{\beta}} &=x_{\bar{\alpha}}^{\mu}x_{\nu}^{\bar{\beta}}\partial_{\mu}A^{\nu},\\
\Gamma_{\bar{\alpha}\bar{\gamma}}^{\bar{\beta}} &=x_{\nu}^{\bar{\beta}}x_{\bar{\alpha}\bar{\gamma}}^{\nu},\\
\partial_{\bar{\beta}}g_{\bar{\alpha}\bar{\gamma}}-g_{\bar{\delta}\bar{\gamma}}\Gamma_{\bar{\beta}\bar{\alpha}}^{\bar{\delta}}-g_{\bar{\alpha}\bar{\delta}}\Gamma_{\bar{\beta}\bar{\gamma}}^{\bar{\delta}}&=\left(g_{\bar{\alpha}\bar{\gamma}}\right)_{\bar{\beta}}-g_{\bar{\delta}\bar{\gamma}}x_{\nu}^{\bar{\delta}}x_{\bar{\beta}\bar{\alpha}}^{\nu}-g_{\bar{\alpha}\bar{\delta}}x_{\nu}^{\bar{\delta}}x_{\bar{\beta}\bar{\gamma}}^{\nu}
 \\&=\left(g_{\bar{\alpha}\bar{\gamma}}\right)_{\bar{\beta}}-\left(x_{\bar{\gamma}}\right)_{\nu}x_{\bar{\beta}\bar{\alpha}}^{\nu}-\left(x_{\bar{\alpha}}\right)_{\nu}x_{\bar{\beta}\bar{\gamma}}^{\nu}+x^{\bar{\delta}}\left[\left(g_{\bar{\delta}\bar{\gamma}}\right)_{\nu}x_{\bar{\beta}\bar{\alpha}}^{\nu}+\left(g_{\bar{\alpha}\bar{\delta}}\right)_{\nu}x_{\bar{\beta}\bar{\gamma}}^{\nu}\right],\\
\partial_{\nu}g_{\mu\rho}-g_{\sigma\rho}\Gamma_{\nu\mu}^{\sigma}-g_{\mu\sigma}\Gamma_{\nu\rho}^{\sigma} &=\left(g_{\mu\rho}\right)_{\nu}.\end{align}$$(Here, some subscripts indicate partial derivatives.)
