EDIT: There's not enough space in the comments to answer Jesse's question below so I answer it here. I haven't thought the construction exactly through, but it should work like this: the Borel space is $X:=${0,1}${}^{G/H}$, and the action is induced by action of $G$ on $G/H$. There's a theorem (of Kaimanovich?) which says that if there is a graphing of a relation such that each component is of subexponential growth then the relation is amenable. In our case connected components are Schreier graphs so our relation is amenable, no matter what measure we put on the Borel space.
The measure is not the product measure. In $G/H$ we have (disjoint) images $C_i$ of $[G:N(H)]$ cosets of $N(H)$. Call $C_i$ "cosets" as well. The measure is supported on those sequences which are non-zero on at most one of the cosets $C_i$. So as a measure space $X$ is the union of $[G:N(H)]$ spaces {0,1}${}^{C_i}$. On each of these subspaces of $X$ the measure is defined to be the product measure normalized by $\frac{1}{[G:N(H)]}$.
The action is not essentially free, because H stabilizes {0,1}${}^C_0$, where $C_0$ is the trivial coset of $N(H)$.
I'm not sure about faithfulness, if I find a good argument why it's faithful I'll add it here. Also, I don't see anymore why I wanted $H$ to have no finite index subgroups which are normal in $G$, although it seemed important to us when we discussed it couple of days ago...

