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.