Here is an example where it is hard in a proof-theoretic sense to determine whether a set is countable.

Jan Reimann and Theodore A. Slaman (in the paper Randomness for continuous measures) study randomness with respect to continuous measures on $2^\mathbb N$.

They show that for every $n$, the set NCR$_n$ of elements of $2^\mathbb N$ that are not $n$-random (Martin-Löf random relative to the $n$th iterate of the halting problem) with respect to any continuous probability measure, is countable. Furthermore, they show that for every $k\in\mathbb N$, there exists $n\in\mathbb N$ such that the statement

NCR$_n$ is countable

cannot be proven in the theory

ZFC$^-$ + "There exists $k$ iterates of the power set of $\mathbb N$",

where ZFC$^-$ denotes Zermelo-Fraenkel set theory with choice, minus the power set axiom.

In other words, if you don't want to assume that the sets $\mathbb N$, $\mathcal P(\mathbb N)$, $\mathcal P(\mathcal P(\mathbb N))$, ... exist then you cannot prove that all but countably many real numbers look random w.r.t. some probability distribution.