¿Adobe?

La mejor manera de fijar un aplacado de piedra en este tipo de pared sería utilizando una preparación previa con mortero. Realizas un enfoscado duro de 1 parte de cemento por cada 2 partes de arena. Primero hay que picar bien el adobe para quitar todas las partes poco resistentes, y dejar sólo la parte del adobe que se encuentre en perfectas condiciones. En el enfoscado puedes reforzar con una malla metálica, de las que existen para armar este tipo de estructuras (una fina malla de alambre que se coloca en el interior mismo del grueso de mortero). Por encima de este preparado ya puedes colocar la piedra. Quedará mejor fijada si utilizas cemento-cola específico para piedra o uno estándar.
Para la cueva, la solución es similar. Puedes utilizar el mortero armado. Si quieres mayor seguridad podrías encargar a una empresa de las que construyen piscinas que te protegieran la cueva con una capa de hormigón proyectado. Colocan la armadura en la pared y luego proyectan a alta presión el hormigón, que queda adherido. Con esta solución sería como tener una pared de hormigón armado que aguanta la pared natural de la cueva. Este sistema es el que se utiliza en los túneles de carreteras y vías directamente excavados en la roca.