I don't know if this is an answer, but it is too long to be a comment, so I am entering it this way. A future paper of Ackermann, Freer and Patel will be about roughly this subject.
From what I understand they give necessary and sufficient conditions for constructing invariant measures on first order structures. Their condition is roughly that the "definable closure" is trivial, where I put this in quotes because it is not what we normally think of in model theory. In the following, letters represent (possibly) tuples, not just singletons. For a structure $\mathcal M,$ we define $a \in dcl (b)$ if given $\sigma \in Aut (\mathcal M /b)$, $\sigma (a)=a.$ In the case that we demand $\mathcal M$ is saturated, this matches the normal definition. But, in unsaturated structures, this need not be the case. Consider, for instance, a structure with countably many descending nested predicates, $P_n$ with $\mathcal M$ a structure so that there is a single point in the intersection $\cap _n P_n$. Of course, such an element is fixed by any automorphism, but is not definable over any set which does not include it.
Restrict, for the moment to a countable language. Then the dcl given above is equivalent to $a \models \psi (x,b)$ and $x \models \psi (x,b) \rightarrow x=a,$ but where $\psi \in \mathcal L_{\omega _1 ,\omega }.$ Make the appropriate modifications when in a larger language (change the $\omega_1$).
Their conditions says that an invariant measure exists when dcl is trivial (meaning $dcl(a)=a$). So, for instance, these structures must be relational.
I don't think a preprint is publicly available yet, and I don't know the method of the proof, but if it is constructive in some way, it might shed some light on the question you have asked. Of course, it would be an interesting question to ask if there is a natural first order (or as in this case) slightly more general condition to add to theirs in order to get an ergodic measure.
