Well... $A^\mu$ is not really a tensor. The tensor form of that 4-potential is
$$
A = A^\mu \partial_\mu,\ A^\mu \in \mathbb{R}
$$
So since you know that $\partial_\mu$ transform as a tensor, then $A$ is a tensor and you say that its components transform as a tensor. Let me explain this a little bit more:
Let's say I want to change coordinates $x \rightarrow y$, then
$$
\partial_\mu = \frac{\partial}{\partial x^\mu} \rightarrow \partial_\mu^{\ '} = \frac{\partial y^\nu}{\partial x^\mu}\frac{\partial}{\partial y^\nu}
$$
Therefore, since $A^\mu$ is just a function, under this change
$$
A(x) = A^\mu(x)\partial_\mu \rightarrow A^{'}(y) = A^{'\ \mu}(y)\frac{\partial y^\nu}{\partial x^\mu}\frac{\partial}{\partial y^\nu}, \quad A^{' \mu}(y) = A^\mu(x(y))
$$
And now you can make an abuse of language and say that $A^\mu$ is a tensor because it transforms as
$$
A^\mu(x) \rightarrow A^{'\ \mu}(y)\frac{\partial y^\nu}{\partial x^\mu}
$$
Now, how do you know that $A^\mu = (\phi , \vec{A})$ gives you the correct theory? As far as I know, that is due to a special relativity extension of classical lagrangian mechanincs. Classically you have that the interaction is given as
$$
S_{int} = \int dt\ L_{int} = -\int dt\ \phi
$$
Since $S$, the action, must be invariant under Lorentz tranformation you suggest that $\phi$ is the zero-th component of some 4-vector $A^\mu = (\phi, \vec{0})$ so now you can write
$$
S_{int} = -\int dt\ A^0 = -\int dx_0\ A^0
$$
But this is not a Lorentz scalar, so you extend $A^\mu = (\phi, \vec{A})$ but without assuming that $\vec{A}$ is the usual magnetic vector potential. Therefore,
$$
S_{int} = -\int dt\ A^0 \xrightarrow{extension} -\int dx_\mu\ A^\mu = -\int dt\ \frac{dx_\mu}{dt}A^\mu
\tag1$$
This is now a Lorent scalar (so invariant) since the index $\mu$ is dummy now. Let's see what $\vec{A}$ is by developing Eq. (1) (recall $x_0 = dt$):
$$
S_{int} = -\int dt\ \phi(dt/dt) - \vec{A}(d\vec{x}/dt)
$$
The part on $\vec{A}$ is the usual interaction of the form current times magnetic potential if consider $\vec{A}$ like that and goes to lagrangian density formulation. By construction $A^\mu$ must be a 4-vector (tensor of rank 1) because if it wasn't that, $A^\mu dx_\mu$ wouldn't be a Lorentz scalar