The answer is yes, such an action exists.

What is needed for the construction is the following very nice example of an action of a non-amenable group on $\mathbb Z$, which I just learned from Gabor Elek.

Consider a graph with vertices given by $\mathbb Z$ and unoriented edges between $n$ and $n+1$.

Pick a random labelling of the edges by the letters $a,b$ and $c$ with no $a$, $b$ or $c$ adjacent to the same letter. This defines an action of the group $G=\mathbb Z/2 \mathbb Z \ast \mathbb Z/2 \mathbb Z \ast \mathbb Z/2 \mathbb Z$. Indeed, just act according to existing labels or fix the element.

This action has the nice feature that it keeps invariant *all* counting measures on $\mathbb Z$, i.e. *all* $\mathbb Z$-Folner sequences sets are also Folner sequences for the $G$-action.

Now, the space of labellings (as above) of the graph is itself a probability measure space (a Bernoulli space), which carries an ergodic p.m.p. $\mathbb Z$-action by shifting. It is easy to see that $G$ acts on this space by measure preserving transformations (just by the method described above, done orbit by orbit) and induces an action as required. Indeed, the orbits are just the $\mathbb Z$-orbits, so its ergodic and amenable. Faithfulness follows the fact that you considered all labellings, so that with positive probability (on the space of labellings), an element will act non-trivially. Note also that $G$ is not amenable.

**EDIT:** As requested, more details on the action. The elements of the shift space are maps $f: \mathbb Z \to \lbrace a,b,c \rbrace$ with $f(n) \neq f(n+1)$. A letter shifts $f$ to the right if $f(1)$ equals that letter, it shifts to the left, if $f(0)$ is equal to the letter; otherwise you fix $f$. It is obvious that the orbits are just the orbits of the shift-action of $\mathbb Z$. Hence, the induced equivalence relation is just the one induced by the action of $\mathbb Z$.

1more comment