Chuck Miller in [Miller, Charles F., III *On group-theoretic decision problems and their classification*. Annals of Mathematics Studies, No. 68. Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971] proves the following two rather nice and natural examples.

**Theorem III.10.** The free product of two free groups with finitely generated amalgamation can have unsolvable conjugacy problem. Further, the finitely presented HNN extension of a free group can have unsolvable conjugacy problem.

(Note that Miller calls HNN extensions 'Strong Britton extensions').

Now by Bass-Serre theory, there is a natural action of an amalgamated free product/HNN on the associated Bass-Serre tree, which should satisfy your "natural action" criterion.