Cantor's diagonalization construction, on a certain view, furnishes functions $$d_X:{\rm Injections}(X,P(X))\rightarrow P(X)$$ that satisfy $\forall X\forall i\ \ d_X(i)\not\in i(X)$
In ZF, can one prove the existence of such functions with the added requirement that $d_X(i)$ actually depends only on the image $i(X)$?
If there is such a function then there is an injection from $\omega_1$ to $2^{\omega}$.
(Set $\: X = \omega \:$, $\:$ send the finite ordinals to the corresponding singletons,
then extend to $\omega_1$ with transfinite recursion.)
If there is such a function and the continuum hypothesis holds then $\: 2^{\aleph_0} = \aleph_1 \:$.
It is consistent with ZF that the continuum hypothesis holds and $\: 2^{\aleph_0} \neq \aleph_1 \:$.
Therefore ZF does not prove the existence of such a function.
Joel David Hamkins, Asaf Karagila and I have made some progress characterizing which sets have such a function. There is still one open case left, but Joel's conjecture holds so far.
Let $[Y]^{X}$ denote the set of all $A \subseteq Y$ such that $A \approx X$. The question is to characterize the sets $X$ for which there is a function $d:[\mathcal{P}(X)]^{X}\to\mathcal{P}(X)$ such that $d(A) \notin A$ for all $A \in [\mathcal{P}(X)]^X$. We will instead try to answer the more general question when there is such a function $d:[Y]^X\to Y$ for arbitrary sets $X, Y$ with $X \preceq Y$. (If $X \npreceq Y$ then $[Y]^X = \varnothing$ and the question is not interesting.) An obviously necessary condition is that $\newcommand{\napprox}{\not\approx}X \napprox Y$ but this is not sufficient as Ricky illustrated. Joel conjectured that such a function exists if and only if $\aleph(X) \preceq Y$, where $\aleph(X)$ is the Hartog number of $X$, the smallest ordinal that does not inject into $X$. We will show that this conjecture is true for all Dedekind infinite sets $X$ (i.e. when $\aleph_0 \preceq X$). Since the statement is obviously true when $X \prec \aleph_0$, the only remaining case is when $X$ is infinite but Dedekind finite (i.e. when $n \prec X$ for every $n \prec \aleph_0$ but $\aleph_0 \npreceq X$).
If there is an injection $f:\aleph(X)\to Y$, then there is such a $d:[Y]^X\to Y$ can be defined as $d(A) = f(\alpha_0)$ where $\alpha_0 = \min\lbrace \alpha \lt \aleph(X) : f(\alpha) \notin A\rbrace$. This last set is always nonempty otherwise composing $f:\aleph(X)\to A$ with a bijection from $A$ onto $X$ contradicts the fact that $\aleph(X) \npreceq X$.
For the converse, the hope is to define an injection $f:\aleph(X)\to Y$ by transfinite recursion where at each stage $\alpha\lt\aleph(X)$, we choose some $f(\alpha) \notin \lbrace f(\beta) : \beta \lt \alpha \rbrace$. To make these choices we would need a function $\hat{d}:[Y]^{\prec\aleph(X)}\to Y$ such that $\hat{d}(A) \notin A$ for every $$A \in [Y]^{\prec\aleph(X)} \colon= \lbrace Z \subseteq Y : Z \prec \aleph(X)\rbrace.$$ What we are given is a function $d:[Y]^X\to Y$ with $d(A) \notin A$ for every $A \in [Y]^X$. A simple idea is to fix some $A_0 \in [Y]^X$ and define $$\hat{d}(A) = d(A \cup A_0)$$ for all $A \in [Y]^{\prec\aleph(X)}$ but this only makes sense when $A \cup A_0 \approx X$. In general, we only know that $$X \preceq A \cup A_0 \preceq A + X,$$ so this strategy will work provided that $\alpha + X \approx X$ for every $\alpha \lt \aleph(X)$. This last statement holds precisely when $X$ is empty or Dedekind infinite. Indeed, $X \approx 1+X$ already implies that $X$ is Dedekind infinite and then $X \approx \alpha + X$ follows from the fact that $\alpha + \alpha \preceq \max(\aleph_0,|\alpha|)$ for every ordinal $\alpha \lt \aleph(X)$.
Asaf Karagila and I have made a little more progress on the case where $X$ and $Y$ are both Dedekind finite. In that case $Y \approx X + Z$ and the complement in $Y$ of any element of $[Y]^X$ has size exactly $Z$ and vice versa. Therefore, the existence of a $d:[Y]^X\to Y$ such that $d(A) \notin A$ for each $A \in [Y]^X$ is precisely equivalent to the existence of a choice function $c:[Y]^Z \to X$. In particular, if $Y \approx X+1$ then there is such a $d:[Y]^X \to Y$ since there clearly is a choice function $c:[Y]^1\to Y$. This does contradict the extension of Joel's conjecture to arbitrary $Y$ but not Joel's original conjecture where $Y = \mathcal{P}(X)$. Unfortunately, we still do not know what happens when $X$ and $Y = \mathcal{P}(X)$ are both infinite but Dedekind finite.
The existence of choice functions $[Y]^Z\to Y$ is a very intricate problem. For example, it is known that the existence of a choice function $[Y]^2\to Y$ is equivalent to the existence of a choice function $[Y]^4\to Y$ but that this does not imply the existence of a choice function $[Y]^3\to Y$! These intricate implications have been examined by John Conway in the article Effective implications between the "finite" choice axioms [Cambridge Summer School in Mathematical Logic, Lecture Notes in Mathematics 337 (1973), 439–458. MR0360275, doi:10.1007/BFb0066784].
Let me point out that in the case $X=\mathbb{N}$, the assertion seems to be simply equivalent to the existence of an injection $\omega_1\to \mathbb{R}$. Ricky has cleverly proved the forward implication. But conversely, if there is a such an injection of $\omega_1\to\mathbb{R}$, then we can define $d_X(i)$ to be the first real not in $i(X)$.
This idea generalizes to higher well-ordered cardinals as well. If $X=\kappa$, then the existence of a map as you request is equivalent to the existence of an injection $\kappa^+\to P(\kappa)$. Ricky's argument again gives the forward direction, and conversely, if there is an injection $\kappa^+\to P(\kappa)$, then we can let $d_X(i)$ be the first set on the list not in $i(X)$.
Perhaps it is true that for any set $X$, the property on $X$ is equivalent to the assertion that the Hartog number $\aleph(X)$, the first ordinal not embedding in $X$, injects into $P(X)$. The converse direction is the same as above, but it isn't clear to me whether one can push Ricky's argument through for this.
