For this problem, we shall use $\mathbb{N}$ instead of $\mathbb{Z}$ since $\mathbb{N}$ is easier to work with in this case. We shall say that $A$ has property $P$ almost everywhere (or for almost all $A$) abbreviated a.e. if $\{A\in P_{0}(X)|A\,\textrm{has property}\,P\}\in\varphi$.`
For $n>0$, let $f_{n}\in\mathcal{A}$ be the function where if $A\in P_{0}(\mathbb{N})$ then $f_{n}(A)$ is the $n$-th element of $A$ whenever $|A|\geq n$ and $f_{n}(A)$ is the last element of $A$ whenever $|A|<n$. Let $y_{n}=x_{f_{n}}$. Then $f_{n}(A)=y_{n}$ for almost every $n$. If $i<j$, then clearly $y_{i}\leq y_{j}$. Furthermore, if $y_{n}=y_{n+1}$, then $f_{1}(A)=y_{1},...,f_{n+1}(A)=y_{n+1}$ for almost every $A\in P_{0}(\mathbb{N})$. However, if $f_{1}(A)=y_{1},...,f_{n+1}(A)=y_{n+1}$, then $A=\{y_{1},...,y_{n+1}\}$ making $\varphi$ a principal ultrafilter. We shall therefore assume that $y_{n}<y_{n+1}$ for all $n$.
We claim that $\varphi$ is an ultrafilter. Let $S=\{A\in P_{0}(X)|f_{1}(A)=y_{1},f_{2}(A)=y_{2}\}$. Then clearly $S\in\varphi$. Let $R\subseteq P_{0}(X)$. Let $h\in\mathcal{A}$ be a function where $h(A)=y_{1}$ for each $A\in R\cap S$ and $h(A)=y_{2}$ for each $A\in R^{c}\cap S$. Then the function $h$ is constant almost everywhere. It is clear that $h(A)=y_{1}$ a.e. or $h(A)=y_{2}$ a.e. If $h(A)=y_{1}$ almost everywhere, then $R\cap S\in\varphi$. If $h(A)=y_{2}$ a.e., then $R^{c}\cap S\in\varphi$. Therefore, we conclude that either $R\in\varphi$ or $R^{c}\in\varphi$. Therefore $\varphi$ is an ultrafilter.
We shall now prove that $\varphi$ is a principal ultrafilter. Assume for the sake of contradiction that $\varphi$ is a non-principal ultrafilter. Let $Y=\{y_{n}|n\in\mathbb{N}\}$. We claim that $Y\not\subseteq A$ for almost every $A$. To prove this assume that $Y\subseteq A$ for almost every $A$. Then the ultrafilter $\varphi$ is $\sigma$-complete. To see this, let $T=\{A\in P(X)|Y\subseteq A\}$, and let $P=\{R_{n}|n\in\mathbb{N}\}$ be a partition of $T$ into countably many pieces. Let $g\in\mathcal{A}$ be a function where if $A\in R_{n}$, then $g(A)=y_{n}$. Then the function $g$ is constant almost everywhere. In particular, $g(A)=y_{n}$ for almost every $A$. However, this implies that $R_{n}\in\varphi$ for some $n$ making the ultrafilter $\varphi$ $\sigma$-complete. On the other hand, it is well known that there are no non-principal $\sigma$-ultrafilters on $P_{0}(\mathbb{N})$ since $|P_{0}(\mathbb{N})|$ is far below the first measurable cardinal if one even exists. We conclude that $Y\not\subseteq A$ for almost every $A$.
Now let $t\in\mathcal{A}$ be a function where if $y_{1}\in A\subseteq\mathbb{N}$ and $Y\not\subseteq A$, then $t(A)=y_{n}$ where $y_{n+1}\not\in A$. Then $t(A)=y_{n}$ for almost all $A\in P_{0}(X)$. Then the function $t$ is constant almost everywhere. In particular, $t(A)=y_{n}$ for almost all $A\in P_{0}(X)$. However, this implies that $y_{n+1}\not\in A$ for almost all $n$. This contradicts the fact that $f_{n+1}(A)=y_{n+1}$ for almost every $A\in P_{0}(X)$. We therefore conclude that $\varphi$ can only be a principal ultrafilter.
$\textbf{Added 5/9/13}$
I mentioned in the comments how this problem can be phrased in terms of uniform spaces. I will now give a topological proof of the fact that every ultrafilter $\varphi$ on $P_{0}(\mathbb{N})$ where every $f\in\mathcal{A}$ is constant $\varphi$-a.e. is simply a principal ultrafilter. The topological proof of this fact that I am about to give is very similar to the purely combinatorial proof of this fact above. In order to translate this problem involving ultrafilters into a problem involving uniform spaces we will need the following result and definitions.
A uniform space $(X,\mathcal{U})$ is said to be non-Archimedean if $\mathcal{U}$ is generated by equivalence relations. For example, if $X$ is a compact space, then there is a unique uniformity $\mathcal{U}$ on $X$ compatible with the topology on $X$ and this uniformity is non-Archimedean if and only if $X$ is totally disconnected.
We define a partition space to be a pair $(X,F)$ where $X$ is a set and $F$ is a filter on the lattice of partitions of $X$. Clearly the partition spaces are in a one-to-one correspondence with the non-Archimedean uniform spaces since the partitions of a set are in a one-to-one correspondence with the filters on that set.
If $(X,F)$ is a partition space, then let $\mathfrak{B}^{*}(X,F)=\{\emptyset\}\cup\bigcup F$. Then $\mathfrak{B}^{*}(X,F)$ is a Boolean algebra. In particular, if $R\subseteq X$, then $R\in\mathfrak{B}^{*}(X,F)$ if and only if $\{R,R^{c}\}\setminus\{\emptyset\}\in F$ if and only if the characteristic function $\chi_{R}$ is uniformly continuous.
An ultrafilter $\mathcal{U}$ on $\mathfrak{B}^{*}(X,F)$ is said to be an $F$-ultrafilter if $\mathcal{U}\cap P\neq\emptyset$ for each $P\in F$.
$\mathbf{Theorem}$ Let $(X,F)$ be a separated partition space. Then the following are equivalent.
$(X,F)$ is complete (as a uniform space,i.e. Every Cauchy filter converges).
Every $F$-ultrafilter on the Boolean algebra $\mathfrak{B}^{*}(X,F)$ is of the form
$\{R\in\mathfrak{B}^{*}(X,F)|x\in R\}$ for some $x\in X$.
$\mathbf{Proof}$(Outline)
$1\rightarrow 2$. If $(X,F)$ is complete and $\mathcal{U}$ is an $F$-ultrafilter, then $\mathcal{U}$ is a Cauchy filter. Therefore $\mathcal{U}$ converges to some point $x\in X$. However, $\{R\in\mathfrak{B}^{*}(X,F)|x\in R\}$ is the only $F$-ultrafilter that converges to the point $x\in X$.
$2\rightarrow 1$. Assume that every $F$-ultrafilter on $\mathfrak{B}^{*}(X,F)$ is of the form $\{R\in\mathfrak{B}^{*}(X,F)|x\in R\}$. Let $Z$ be a Cauchy filter on $X$. Then $Z\cap\mathfrak{B}^{*}(X,F)$ is an $F$-ultrafilter, so $Z\cap\mathfrak{B}^{*}(X,F)=\{R\in\mathfrak{B}^{*}(X,F)|x\in R\}$ for some $x\in X$. It turns out that the filter $Z$ converges to the point $x$. $\mathbf{QED}$
We shall give the space $\mathbb{N}$ the discrete uniformity.
Let $\mathcal{B}=\mathcal{A}\cup\{f:P_{0}(\mathbb{N})\rightarrow\mathbb{N}:|f[P_{0}(\mathbb{N})]|<\infty\}$. In other words, $\mathcal{B}$ is the union of the set $\mathcal{A}$ with the set of all functions $f:P_{0}(\mathbb{N})\rightarrow\mathbb{N}$ with bounded range. Now give $P_{0}(\mathbb{N})$ the coarsest uniformity such that every function $f\in\mathcal{B}$ is a uniformly continuous function. Let $(P_{0}(\mathbb{N}),F)$ be the corresponding partition space structure. Then $\mathfrak{B}^{*}(P_{0}(\mathbb{N}),F)=P(P_{0}(\mathbb{N}))$, and the $F$-ultrafilters are precisely the ultrafilters on the set $P_{0}(\mathbb{N})$ such that every function $f\in\mathcal{A}$ is constant almost everywhere. Therefore by the above theorem, every ultrafilter $\mathcal{U}$ on $P_{0}(\mathbb{N})$ such that every $f\in\mathcal{A}$ is constant $\mathcal{U}$-a.e. is principal if and only if the space $P_{0}(\mathbb{N})$ is a complete uniform space. We shall now prove that the uniform space $P_{0}(\mathbb{N})$ is complete.
Let $L:P_{0}(\mathbb{N})\rightarrow\mathbb{N}^{\mathcal{B}}$ be the function where
$L(A)=(f(A))_{f\in\mathcal{B}}$ for each $A\in P_{0}(\mathbb{N})$. Give $\mathbb{N}^{\mathcal{B}}$ the product uniformity where $\mathbb{N}$ still has the discrete uniformity. Then $\mathbb{N}^{\mathcal{B}}$ is a complete uniform space since the product of complete uniform spaces is always a complete uniform space. Therefore the space $P_{0}(\mathbb{N})$ is complete if and only if the image $L[P_{0}(\mathbb{N})]$ is a complete subspace of $\mathbb{N}^{\mathcal{B}}$. However, the space $L[P_{0}(\mathbb{N})]$ is complete if and only if $L[P_{0}(\mathbb{N})]$ is a closed subspace of $\mathbb{N}^{\mathcal{B}}$. We therefore only need to show that $L[P_{0}(\mathbb{N})]$ is closed in $\mathbb{N}^{\mathcal{B}}$.
Let $(x_{f})_{f\in\mathcal{B}}\in \overline{L[P_{0}(\mathbb{N})]}$. Then since every neighborhood of $(x_{f})_{f\in\mathcal{B}}$ intersects $L[P_{0}(\mathbb{N})]$, whenever $h_{1},...,h_{n}\in\mathcal{B}$ there is some $A\in P_{0}(\mathbb{N})$ where $x_{h_{1}}=h_{1}(A),...,x_{h_{n}}=h_{n}(A)$.
As before, let $f_{n}\in\mathcal{A}$ be the function where $f_{n}(A)$ is the $n$-th element of $A$ whenever $|A|\geq n$ and $f_{n}(A)$ is the last element of $A$ whenever $|A|<n$. Let $y_{n}=x_{f_{n}}$ for all $n$. Then for all $n$, there is some $A\in P_{0}(\mathbb{N})$ with $y_{i}=x_{f_{i}}=f_{i}(A)$ for $1\leq i\leq n$. In particular, since the sequence $(f_{i}(A))_{i\in\mathbb{N}}$ is increasing for all $A$, we conclude that the sequence $(y_{n})_{n\in\mathbb{N}}$ is increasing.
Assume that $x_{f_{n}}=y_{n}=y_{n+1}=x_{f_{n+1}}$ for some $n$. Then there is an $A\in P_{0}(\mathbb{N})$ with $f_{i}(A)=x_{f_{i}}=y_{i}$ for $1\leq i\leq n+1$. Furthermore, one can clearly see that the $A\in P_{0}(\mathbb{N})$ with $f_{i}(A)=x_{f_{i}}=y_{i}$ for $1\leq i\leq n+1$ is unique. In particular $A=\{y_{1},...,y_{n}\}$. Let $U$ be the neighborhood of $(x_{f})_{f\in\mathcal{B}}$ consisting of all systems $(z_{f})_{f\in\mathbb{B}}$ such that $z_{f_{1}}=x_{f_{1}},...,z_{f_{n+1}}=x_{f_{n+1}}$. Then $U$ is an open set, but $U$ intersects $L[P_{0}(\mathbb{N})]$ at only one point, namely the point $L(\{y_{1},...,y_{n}\})=(f(\{y_{1},...,y_{n}\}))_{f\in\mathcal{B}}$. Therefore since $U$ is an open neighborhood of $(x_{f})_{f\in\mathcal{B}}$, $U$ intersects $L[P_{0}(\mathbb{N})]$ at only the point $L(\{y_{1},...,y_{n}\})$, and $(x_{f})_{f\in\mathcal{B}}\in\overline{L[P_{0}(\mathbb{N})]}$, we conclude that
$(x_{f})_{f\in\mathcal{B}}=L(\{y_{1},...,y_{n}\})$.
Now assume that $y_{n}<y_{n+1}$ for all natural numbers $n$. Let $Y=\{y_{n}|n\in\mathbb{N}\}$. We shall now show that $(x_{f})_{f\in\mathcal{B}}=L(Y)$.
We first claim that there is a neighborhood $U$ of $(x_{f})_{f\in\mathcal{B}}$ such that if $L(A)\in U$, then $Y\subseteq A$.
Let $h\in\mathcal{B}$ be the function where $h(A)=1$ if $Y\subseteq A$ and $h(A)=2$ if $Y\not\subseteq A$. Let $t$ be a function where if $Y\not\subseteq A$ and $y_{1}\in A$, then $t(A)=y_{n-1}$ where $n$ is the least natural number with $y_{n}\not\in A$.
I claim that $x_{h}=1$. Suppose to the contrary that $x_{h}\neq 1$. Then there is some $A$ with $h(A)=x_{h},f_{1}(A)=x_{f_{1}}=y_{1},t(A)=x_{t}$.
Since $x_{h}\neq 1$, we have $h(A)=2$, so $Y\not\subseteq A$. Since $f_{1}(A)=y_{1}$, we have $y_{1}\in A$. Therefore by the definition of $t$, we have $x_{t}=t(A)=y_{n-1}$ where $n$ is the least natural number with $y_{n}\not\in A$.
Now, there is some $B\in P_{0}(\mathbb{N})$ with $h(B)=x_{h},t(B)=x_{t}=y_{n},f_{1}(B)=x_{f_{1}}=y_{1},f_{n+1}(B)=x_{f_{n+1}}=y_{n+1}$. Then since $f_{n+1}(B)=y_{n+1}$, we have $y_{n+1}\in B$. However, $f_{1}(B)=y_{1}$, so $y_{1}\in B$ and since $h(B)=x_{h}\neq 1$, we have $Y\not\subseteq B$. Therefore since $t(B)=y_{n}$, we have $y_{n+1}\not\in B$. This is a contradiction. Therefore, we conclude that $x_{h}=1$.
Let $g$ be the function where $g(A)$ is the least element of $A\setminus Y$ whenever $A\not\subseteq Y$ and $g(A)$ is the least element of $A$ whenever $A\subseteq Y$.
We claim that $x_{g}\in Y$. To prove this claim, suppose to the contrary that $x_{g}\not\in Y$. Then $x_{g}<y_{n}$ for some $n$. Thus, there is some $A\in P_{0}(\mathbb{N})$ with $g(A)=x_{g},f_{1}(A)=x_{f_{1}}=y_{1},...,f_{n}(A)=x_{f_{n}}=y_{n}$. Therefore the first $n$ elements of $A$ are $y_{1},...,y_{n}$. This contradicts the fact that $x_{g}\in A\setminus Y$ and $x_{g}<y_{n}$. We therefore conclude that $x_{g}\in Y$.
Now let $U\subseteq\mathbb{N}^{\mathcal{B}}$ be the set where $(z_{f})_{f\in\mathcal{B}}$ if and only if $z_{g}=x_{g}$ and $z_{h}=x_{h}$. Then $U$ is an open neighborhood of $(x_{f})_{f\in\mathcal{B}}$.
If $A\in P_{0}(X)$ and $(f(A))_{f\in\mathcal{B}}=L(A)\in U$, then $g(A)=x_{g}=h(A)=x_{h}$. Therefore $h(A)=x_{h}=1$ and $g(A)=x_{g}\in Y$. Since $h(A)=x_{h}=1$, we conclude that $Y\subseteq A$. However, since $g(A)=x_{g}\in Y$, we conclude that $A\subseteq Y$ as well, so $A=Y$. We conclude that $L(Y)$ is the only possible point in $L[P_{0}(\mathbb{N})]\cap U$. Therefore since $U$ is a neighborhood of $(x_{f})_{f\in\mathcal{B}}$ and
$(x_{f})_{f\in\mathcal{B}}\in\overline{L[P_{0}(\mathbb{N})]}$, we conclude that $(x_{f})_{f\in\mathcal{B}}=L(Y)$. Thus, the set $L[P_{0}(\mathbb{N})]$ is a closed set in $\mathbb{N}^{\mathcal{B}}$.
$\textbf{Added 5/10/13}$
I am now going to completely characterize the cardinalities $|X|$ such that if $\varphi$ is a filter where every function in $\mathcal{A}$ is constant almost everywhere then $\varphi$ is a principal ultrafilter. This characterization is a generalization of the proof that I gave at the top of this post. As one who is familiar with large cardinals might expect, the every such ultrafilter is a principal ultrafilter if and only if $|X|$ is non-measurable.
We say that a cardinal $\lambda$ is non-measurable if there is no non-principal $\sigma$-complete ultrafilter on $\lambda$. This is equivalent to saying that $\lambda$ is below the first measurable cardinal.
$\mathbf{Theorem}$ Let $X$ be a set.
I. Let $\varphi$ be a filter on $P_{0}(X)$ such that every function $f\in\mathcal{A}$ is constant $\varphi$-a.e. Then $\varphi$ is an $\sigma$-complete ultrafilter.
II. $|X|$ is non-measurable if and only if every filter $\varphi$ on $P_{0}(X)$ such that every function $f\in\mathcal{A}$ is constant almost everywhere is a principal ultrafilter.
$\mathbf{Proof}$.
I. For each $f\in\mathcal{A}$, let $x_{f}$ be the constant with $x_{f}=f$ $\varphi$-a.e.
Without loss of generality, assume that $X=\lambda$ for some cardinal $\lambda$. For all $n\in\omega$, let $f_{n}\in\mathcal{A}$ be the function where $f_{n}(A)$ is the $n$-th element of $A$ whenever $|A|\geq n$ and $f_{n}(A)$ is the last element of $A$ whenever $|A|<n$. Let $y_{n}=x_{f_{n}}$ for all $n$. Let $Y=\{y_{n}|n>0\}$. Clearly the sequence $(y_{n})_{n}$ is increasing.
If $y_{1}=y_{2}$, then $\varphi$ is a principal ultrafilter since if $f_{1}(A)=y_{1},f_{2}(A)=y_{2}$, then $A=\{y_{1}\}$, so since $f_{1}(A)=y_{1},f_{2}(A)=y_{2}$ $\varphi$-a.e., we have $\varphi$ be the principal ultrafilter generated by $A$. Now assume that $y_{1}<y_{2}$.`
Let $S=\{A\in P_{0}(\lambda)|f_{1}(A)=y_{1},f_{2}(A)=y_{2}\}$. Then clearly $S\in\varphi$. Let $R\subseteq P_{0}(X)$. Let $h\in\mathcal{A}$ be a function where $h(A)=y_{1}$ for $A\in R\cap S$ and $h(A)=y_{2}$ for $A\in R^{c}\cap S$. Then $h$ is constant almost everywhere and $h(A)\in\{y_{1},y_{2}\}$ for almost every $A\in P_{0}(\lambda)$ and $h(A)=y_{2}$. Therefore $h(A)=y_{1}$ for almost every $A\in P_{0}(\lambda)$ or $h(A)=y_{2}$ for almost every $A\in P_{0}(\lambda)$. If $h(A)=y_{1}$ for almost every $A\in P_{0}(\lambda)$, then $R\cap S\in\varphi$ and if $h(A)=y_{2}$ a.e., then $R^{c}\cap S\in\varphi$. Therefore either $R\in\varphi$ or $R^{c}\in\varphi$. Therefore $\varphi$ is an ultrafilter.
If $y_{n}=y_{n+1}$, and $f_{1}(A)=y_{1},...,f_{n+1}(A)=y_{n+1}$, then clearly $A=\{y_{1},...,y_{n}\}$, but since $f_{1}(A)=y_{1},...,f_{n+1}(A)=y_{n+1}$ for almost every $A$, we conclude that $\varphi$ is the principal ultrafilter generated by $A$.
Now assume that $y_{n}<y_{n+1}$ for all $n$. Let $Y=\{y_{n}|n\in\mathbb{N},n>0\}$. We claim that $Y\subseteq A$ for almost every $A\in P_{0}(\mathbb{N})$. Suppose to the contrary that $Y\not\subseteq A$ for almost every $A\in P_{0}(\mathbb{N})$. Let $t\in\mathcal{A}$ be a function such that if $Y\not\subseteq A$ and $y_{1}\in A$, then $t(A)=y_{n-1}$ where $n$ is the least natural number where $y_{n}\not\in A$. Since $Y\not\subseteq A$ and $y_{1}\in A$ for almost every $A\in P_{0}(\lambda)$, we have $t(A)\in Y$ for almost every $A\in Y$. Since the function $t$ is constant almost everywhere, we conclude that $x_{t}=y_{n}$ for some $n$. Therefore, $t(A)=y_{n},f_{1}(A)=y_{1},f_{n+1}(A)=y_{n+1}$ and $Y\not\subseteq A$ for almost every $A\in P_{0}(\lambda)$. However, this is a contradiction since for such $A$ we have that $t(A)=y_{n},f_{1}(A)=y_{1},Y\not\subseteq A$ implies that $y_{n+1}\not\in A$, but clearly $y_{n+1}=f_{n+1}(A)\in A$. Therefore, we conclude that $Y\subseteq A$ for almost every $A\in P_{0}(\mathbb{N})$.
Since $Y$ is a countable set and $Y\subseteq A$ for almost every $A$, it is now fairly easy to show that the ultrafilter $\varphi$ is $\sigma$-complete. If $P=\{R_{n}|n\in\mathbb{N},n>0\}$ is a partition of $P_{0}(\lambda)$ into countably many pieces, then let $g$ be the function where if $Y\subseteq A$ and $A\in R_{n}$, then $g(A)=y_{n}$. Then $g$ is constant almost everywhere. Furthermore, since $Y\subseteq A$ for almost every $A$, we have $g(A)\in Y$ for almost every $A$. Therefore there is some $n$ where $g(A)=y_{n}$ for almost every $A$. Therefore since $g(A)=y_{n}$ and $Y\subseteq A$ for almost every $A$, and if $g(A)=y_{n}$ and $Y\subseteq A$, then $A\in R_{n}$. Therefore $A\in R_{n}$ for almost every $A$, so $R_{n}\in\varphi$. Since the ultrafilter $\varphi$ selects an element from every countable partition of $P_{0}(\lambda)$, then ultrafilter $\varphi$ is $\sigma$-complete.
II. $\rightarrow.$ If $X$ is of non-measurable cardinality, then $P_{0}(X)$ is of non-measurable cardinality as well. Furthermore, since every filter $\varphi$ such that every function $f\in\mathcal{A}$ is constant almost everywhere is a $\sigma$-complete ultrafilter, we have $\varphi$ be a principal ultrafilter.
$\leftarrow.$ If $X=\lambda$ is of measurable cardinality, then there is some measurable cardinal $\mu$ with $\mu\leq\lambda$. Since every measurable cardinal $\mu$ is $\mu$-supercompact, there is a normal ultrafilter $U$ over $[\mu]^{<\mu}=\{A\subseteq \mu:0<|A|<\mu\}$. Therefore if $\varphi$ is the ultrafilter over $P_{0}(\lambda)$ where $R\in\varphi$ if and only if $R\cap[\mu]^{<\mu}\in U$, then every $f\in\mathcal{A}$ is constant $\varphi$-a.e., but $\varphi$ is a non-principal ultrafilter. $\mathbf{QED}$
