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$.