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

Jan Reimann and Theodore A. Slaman (in the paper [Randomness for continuous measures][1]) 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 <i>all but countably many real numbers look random w.r.t. some probability distribution</i>.


  [1]: http://www.math.psu.edu/reimann/Publications/continuous_randomness_draft.pdf