Despite the claims reported from Wikipedia and the “Earliest Uses” site, this notation certainly started much before Hurewicz-Steenrod (1940; 1941) or Ore (1935, p. 416; 1936) for, respectively, Domain-to-Codomain and Argument-to-Value arrows.
1. Domain $\to$ Codomain (as in the question proper):
Scholz (2008, pp. 883-884) describes manuscripts and lecture notes of Hausdorff (1933):
In these manuscripts he made extensive use of the arrow symbolism for maps. Until that time this was by no means common. Mapping arrows were used only sporadically in the contemporary literature: sometimes (element-to-element) for boundary operators in homology theory [Alexander (1926), Alexandroff (1928), Čech (1932), Pontrjagin (1931)], occasionally also for general homomorphisms [van der Waerden (1930)]. For maps of entire groups, H. Weyl had used them to symbolize representation homomorphisms (1925).
I’m not finding any set-to-set arrows in Weyl (1925). But he has at least one in (1931, p. 267), and van der Waerden (1930; reviewed by Ore in 1932) has indeed, e.g.
(p. 33) $\dots$ eine homomorphe Abbildung $\smash{\mathfrak G\to\overline{\mathfrak G}}\dots$
(p. 87) $\dots$ Die Homomorphie $C\to\mathfrak P\dots$
(p. 190) $\dots$ in der Homomorphie $\smash{\mathfrak R\to\overline{\mathfrak R}}\dots$
(p. 203) $\dots$ eine Zuordnung $\smash{\mathsf P(\mathfrak A)\to \mathsf P(\mathfrak A')}\dots$ nämlich die Zuordnung $\alpha\to\alpha'\dots$
McLarty (2006, p. 200) argues that the first one at least was only “a prescient typographical error” for a Nœther tilde $\sim$. But I’m not sure I buy this, as there are more and this is unchanged in later editions (1955, 1971, 1993).
2. Argument $\to$ Value (nowadays written $\mapsto$, with other antecedents):
These are much older. All references above have many, but the earliest I’ve seen are shaped $\rightarrowtail$ and occur in perhaps the earliest commutative diagram, by Eduard Study (1891, p. 508). The next are again in papers of Study, (1905):
(p. 432) $\dots$ eine umkehrbahre analytische Zuordnung $(E\to E')$ $\dots$
(p. 435) $\dots$ die Zuordnung der Strahlen $(S\to S')$ $\dots$
(p. 438) $\dots$ die Transformation $(S\to S')$ kann zu einer orientierten $\dots$
(p. 438) $\dots$ Berührungstransformation $(E\to E')$ erweitert werden $\dots$
and (1906, pp. 493-496, 511-516). Blaschke (1910a, 1910b) adopts them throughout, as do books by Blaschke-Study (1911/13, pp. 15, 17, 23, etc.), Weyl (1913, e.g. pp. 32, 50, 54, 139, 159), Speiser (1923, e.g. pp. 38, 88, 103), or again Study (1923). There, §1 “Grundbegriffe und Zeichen” (p. 16) sounds much like he’s claiming the notation, while crediting Wiener (1890) for another:
As you noticed, the iterative conception of sets requires a pre-existing universe of sets, and ordinals with which we can label the stages. So if you work within ZFC itself, in other words within an existing model of ZFC, you can perform that iterative construction to obtain $V$. Like Asaf Karagila says here, you cannot get nothing from nothing. Typically, in set theory you work in ZFC, where you have ordinals, and construct $V_k$ for each ordinal $k$. Note that $V$ is not a set, but the entire universe (the one you are working in).
I still think your question is mainly philosophical, your comment to Nik Weaver notwithstanding. After all, you ask:
First of all, the Power Set operation is not absolute, that is it varies between models of ZFC.
Of course, since ZFC proves that $V$ is the whole universe, different models of ZFC will have different $V$. If ZFC is consistent, then it has a countable model $V$. That should not be surprising; one can never 'pin down' the set-theoretic universe, not to say using $V$. The same issue shows up with the natural numbers, as Asaf alluded to in a comment; second-order PA with full semantics does not 'pin them down' because our meta-system MS must always be computable, and hence even if MS has (proves existence of) a full semantics model of second-order PA, there are models of MS whose interpretation of the naturals are not isomorphic (if there are any models at all).
In order to define the Universe of Sets we must begin with a concept of ordinals, but in order to define the ordinals we need to have a concept of the Universe of Sets! So my question is to ask: Is this definition circular?
We cannot define anything, much less whatever is meant by a "universe of sets", without already working under some assumptions. It is not necessary that you work in ZFC, but what other alternative meta-system do you have in mind? Remember that to construct $V$ you need all those set-theoretic operations that you are using, plus the collection of ordinals, and any meta-system that supports all these is going to look very much like ZF or some extension of it.
Boolos noted the same philosophical circularity in this paper (page 15) (which I rephrased to the language used here and emphasized some points):
There is an extension of the stage theory from which the axioms of replacement could have been derived. We could have taken as axioms all instances of a principle which may be put, 'If each set is correlated with at least one stage (no matter how), then for any set $z$ there is a stage $s$ such that for each member $w$ of $z$, $s$ is later than some stage with which $w$ is correlated'.
This bounding or cofinality principle is an attractive further thought about the interrelation of sets and stages, but it does seem to us to be a further thought, and not one that can be said to have been meant in the rough description of the iterative conception. For that there are exactly $ω_1$ stages does not seem to be excluded by anything said in the rough description; it would seem that $V_{ω_1}$ (see below) is a model for any statement that can (fairly) be said to have been implied by the rough description, and not all of the axioms of replacement hold in $V_{ω_1}$. (*) Thus the axioms of replacement do not seem to us to follow from the iterative conception.
(*) Worse yet, $V_{δ_1}$ would also seem to be such a model. ($δ_1$ is the first uncomputable ordinal.)
To put it more cogently, if you take for granted the power-set operation as a primitive, and start with the empty-set, and also take for granted the ability to consolidate into a single operation the union of any iteratively generated sequence of sets, which may itself be used iteratively to generate more sets, then what you can generate appears to be entirely contained within $V_{δ_1}$. And if you additionally allow taking union of arbitrary (countable) and potentially indescribable sequences, then what you can generate is still contained within $V_{ω_1}$.
The crux is that you cannot generate $V_{ω_1}$ without essentially having $ω_1$. And this corresponds to two logical facts: that there is no countable sequence of ordinals before $ω_1$ whose union is $ω_1$, and that $V_{ω_1}$ is a model of ZF with replacement restricted to countable sequences.
More philosophically, if you envision the stages as being generated rather than pre-existing, then necessarily you cannot generate stage $ω_1$ until you have generated all the stages corresponding to countable ordinals. But there is no way to generate all countable stages without having a generation process that already has length at least $ω_1$. And since $ω_1$ does not appear in any stage up to $V_{ω_1}$, you have no choice but to assume the ability to 'run a generation process' of length $ω_1$ if you want to obtain $V_{ω_1}$ and further stages, which implies that the iterative conception cannot give ontological justification for the existence of $ω_1$.
Just to add, it is true that uncountable well-orderings do appear much earlier than $V_{ω_1}$, but the very fact that $ω_1$ does not appear even at stage $ω_1$ (union of all prior stages) should be a warning that one should not consider all well-orderings of the same length to be on equal footing. In particular, to have a well-ordering as a binary relation on a set that makes it totally ordered with no strictly descending sequence is not the same as being able to iterate along it.
Perhaps someone may find a non-circular way to justify ZFC philosophically, but the iterative conception seems to get us no further than countable replacement.
Best Answer
Charles Sanders Peirce is credited with the beth notation ℶ, first introduced in a December 1900 letter to Cantor. Apparently, this was then forgotten for half a century.
I reproduce the relevant text from Gregory Moore's Early history of the generalized continuum hypothesis.