What guarantees constructive proofs of existence of finitely additive probability measures? Disclaimer. This question is closely related to an older question of mine. I felt it was important to write a new question because (i) the older question wasn't sufficiently clear to begin with, and adding more content to it might make things even messier; (ii) there are a few important technical differences between this question and the older one.
Let $\Omega$ be a set and let $\mathcal{A}$ be an algebra of subsets of $\Omega$. Roughly, my question is

What properties must the space $(\Omega, \mathcal{A})$ have in order for us to prove "constructively" that there exists a "non-trivial" finitely additive probability measure on it?

We might think of this as a "question schema" from which a variety of related questions arise upon specifying what one means by "constructively" and "non-trivial." Let me give a trivial example.
Let "non-trivial" mean that $P(A)>0$ for all nonempty $A$, and let "constructively" mean "using only the ZF axioms." Then, of course, it is sufficient that $\Omega$ be finite and $\mathcal{A} = 2^\Omega$. 
There are challenges once we move beyond finite state spaces, however. Consider $(\mathbb{N}, 2^{\mathbb{N}})$. If by "non-trivial" we mean that $P(n)=0$ for all $n \in \mathbb{N}$, and by "constructively" we mean the same as before, then it turns out that we cannot prove constructively that a non-trivial $P$ exists.
In fact, as Asaf Karagila pointed out to me, there is a general result that says the Hahn-Banach theorem is equivalent to the assertion

Every Boolean algebra supports a finitely additive probability measure.

As Hahn-Banach is stronger than the ZF axioms (but weaker than ZF+AC), it seems we must be willing to move beyond ZF if we want to guarantee that finitely additive probabilities always exist. But note: this result doesn't give us any information about when axioms beyond ZF will be needed, and it doesn't address the non-triviality issue.
In other words, it doesn't help with the following sort of question, which will be my final example of filling in the "schema" above. Suppose I want to define a non-atomic probability on a "rich" space. For example, both $\Omega$ and $\mathcal{A}$ should be at least countably infinite. So "non-trivial" here means non-atomic, and "constructively", as usual, means "using only ZF," and the question schema becomes

What properties must $(\Omega, \mathcal{A})$ have, in addition to being at least countably infinite, in order to prove in ZF that there exists a non-atomic finitely additive probability measure on $(\Omega, \mathcal{A})$?

Obviously, what I've been asking about is very open-ended since there are various ways to define "non-trivial" and "constructively." I don't expect anything like a comprehensive answer. I'm just hoping for insights, partial results, and further examples.
 A: If $\mathcal{A}$ is a $\sigma$-algebra, the problem reduces to finding a countably additive probability measure, because every probability measure that fails to be countably additive gives you a finitely additive probability measure on every subset of the natural numbers that vanishes at the singletons. As you have pointed out, such an object is highly non-constructive.
So let $\mu$ be a finitely additive probability measure on the measurable space $(\Omega,\mathcal{A})$ that fails to be countably additive. Then there must be a disjoint sequence $\langle A_n\rangle$ in $\mathcal{A}$ such that
$$\sum_n \mu(A_n)<\mu\bigg(\bigcup_n A_n\bigg).$$ Now define the function $\nu$ on $2^\mathbb{N}$ by letting $$\nu(F)=\frac{\mu\big(\bigcup_{n\in F} A_n\big)-\sum_{n\in F}\mu(A_n)}{\mu\big(\bigcup_n A_n\big)-\sum_n\mu(A_n)}.$$
This function is clearly finitely additive, satisfies $\nu(\mathbb{N})=1$ and, since $\mu$ is finitely additive, $\nu(F)=0$ if $F$ is finite. You can find this construction under "Pincus's Pathology" in Schechter's book.
So you either look for countably additive probability measures only or finitely additive probability measures that are defined on algebras that are not $\sigma$-algebras. Everything else is wildly non-constructive.
