The answer is yes, under the axiom of choice, such a partition is possible. There are several ways of seeing this. For example, choice gives us that any set is in bijection with an infinite ordinal. But, for any infinite ordinal $\alpha$, there is a bijection between $\alpha$ and $\alpha\times \{1,\dots,n\}$. The bijection is in fact canonical, in the sense that there is a "uniform" procedure that applied to any infinite ordinal $\alpha$ produces such a bijection. If you are somewhat familiar with ordinal numbers, a proof can be found in this blog post of mine.
Of course, if $\alpha$ is in bijection with $X$, then $\alpha\times \{1,\dots,n\}$ is in bijection with $X\times \{1,\dots,n\}$, so the latter is in bijection with $X$. The required partition is then the image under the bijection of the sets $A_a=\{(a,i)\mid 1\le i\le n\}$, for $a\in X$.
(To mention but one other standard argument, using choice, we have that $X$ and $X\times X$ are in bijection so, invoking the Bernstein-Schroeder theorem, we conclude that $X$ and $X\times\{1,\dots,n\}$ are in bijection as well.)
On the other hand, the answer is no, without the axiom of choice it is in general not possible to produce such a partition. This is addressed at length in this MO answer, with details in the references linked there.
First, let me address your question about provability. It is in fact quite easy to exhibit a pair of sequences of rationals $C_1, C_2$ such that
ZFC (indeed, much less) proves that exactly one is a Cauchy sequence, but
ZFC doesn't prove that $C_1$ is Cauchy and ZFC doesn't prove that $C_2$ is Cauchy.
Semantically speaking, in every model of ZFC, one of $C_1$ and $C_2$ is Cauchy, but both possibilities can occur.
Specifically:
Let the $i$th term of $C_1$ be $i$ if the continuum hypothesis holds, and $0$ if the continuum hypothesis fails.
Let the $i$th term of $C_2$ be $i$ if the continuum hypothesis fails, and $0$ if the continuum hypothesis holds.
ZFC proves that $C_1$ is Cauchy iff CH fails, and ZFC proves that $C_2$ is Cauchy iff CH holds, but ZFC does not decide CH so ZFC cannot tell which of $C_1$ and $C_2$ is Cauchy.
Next, let's sketch a ZFC proof (indeed, vastly less than ZFC) that the set of equivalence classes of Cauchy sequences - which I'll denote "$\mathbb{R}_C$" - is indeed uncountable. This is just Cantor's first argument superficially rephrased, but you might find this rephrasing helpful.
Specifically, for a Cauchy sequence $C=(c_i)_{i\in\mathbb{N}}$ and rationals $p<q$, say that $C$ avoids the interval $[p, q]$ if for some $n\in\mathbb{N}$ we have $$\forall m>n(c_m\not\in [p,q])$$ (that is, if $C$ eventually leaves $[p,q]$ and never comes back). It's a good exercise to show that whenever $p<q, r<s$ are rationals with $[p,q]\cap [r,s]=\emptyset$ (that is, either $p<q<r<s$ or $r<s<p<q$) we either have $C$ avoids $[p,q]$ or $C$ avoids $[r,s]$ (or both).
Next, we'll define a pair of operations on closed intervals with rational endpoints: for $[a, b]$ a closed interval with rational endpoints, let $$Left([a,b])=[a, a+{b-a\over 3}]\quad\mbox{and}\quad Right([a,b])=[b-{b-a\over 3}, b].$$ (Think about the construction of the Cantor set.)
Now we're ready to diagonalize (if we assume Choice; if not, we neeed an extra step, which I've outlined below). Suppose $(\mathbb{E}_i)_{i\in \mathbb{N}}$ is a sequence of equivalence classes of Cauchy sequences. Pick (via Choice) a representative $C_i=(c_j^i)_{j\in\mathbb{N}}$ of each $\mathbb{E}_i$.
We now define a sequence of closed intervals $(I_i)_{i\in\mathbb{N}}$ as follows:
Now let $a_n$ be the left endpoint of $I_n$, and consider the sequence $A=(a_n)_{n\in\mathbb{N}}$. It's easy to check that this is Cauchy and not equivalent to any $C_i$; thus, the equivalence class $\mathbb{A}$ of $A$ is not in $\mathbb{E}$, and this completes the proof.
If we didn't assume choice, the passage from $(\mathbb{E}_i)_{i\in\mathbb{N}}$ to $(C_i)_{i\in\mathbb{N}}$ appears problematic at first. However, we do in fact have a canonical way to pick representatives of equivalence classes.
Namely, suppose $\mathbb{E}$ is an equivalence class of Cauchy sequences. Fix an enumeration $(q_i)_{i\in\mathbb{N}}$ of $\mathbb{Q}$, let $p_i$ be the rational with minimal index such that some (equivalently, every) element of $\mathbb{E}$ does not avoid $[p_i, p_i+{1\over i}]$, and let $C=(p_i)_{i\in\mathbb{N}}$. It's a good exercise to check that this is well-defined and is a Cauchy sequence in $\mathbb{E}$.
Finally, a comment on definability and models.
What the above shows is that ZFC (indeed, much less) proves that the set of equivalence classes of Cauchy sequences of rationals is uncountable. This means that whenever $M$ is a model of ZFC (externally countable or not), there is no bijection in $M$ between what $M$ thinks is the set of Cauchy sequences and what $M$ thinks is $\mathbb{N}$. Of course, such a bijection might exist in reality (= externally).
Moreover, this does not contradict the possibility of every Cauchy sequence in $M$ being definable in $M$; this is a special case of the fact that pointwise definable models (which you mention) can exist. The map sending a Cauchy sequence in $M$ to a definition in $M$ of that Cauchy sequence is not definable in $M$ (per Tarski), and so we don't get a contradiction with the internal uncountability of the set of equivalence classes of Cauchy sequences.
Best Answer
For every rational $q$ let $A_q^+=\{x\in A\mid x\geq q\}$ and $A_q^-=\{x\in A\mid x<q\}$. If for some $q$ both are uncountable, super. If not, what can you say about $A$ itself?
Now, you might wonder as to the use of the axiom of choice here, and it hides beneath the surface: in order to prove that every countable union of countable sets is countable, we have to use the axiom of choice.
Edit: Let $r=\sup\{q\mid A^-_q\text{ is countable}\}$ and $s=\inf\{q\mid A^+_q\text{ is countable}\}$.
If either $r$ or $s$ is not a real number (i.e., $\pm\infty$) then we get that $A$ is countable.
If $r>s$, take a rational $q$ witnessing that, then $A^-_q$ and $A^+_q$ are both countable, what do we get?
If $r<s$, take a rational $q$ witnessing that, then $A^-_q$ and $A^+_q$ are both uncountable.
Finally, if $r=s=q$, take an increasing sequence of rationals $r_n$ and a decreasing sequence of rationals $s_n$, both converging to $q$. Then $A\cap\bigcup_{p<q}A_p^+=A\cap\bigcup_{n\in\Bbb N}A^+_{r_n}$ is countable; and $A\cap\bigcup_{p>r} A^-_p$ is countable. Again, we get that $A$ is countable.
So if $A$ is uncountable, there is a rational $q$ such that $r<q<s$ and $A_q^-$ and $A^+_q$ are both uncountable.