How about milk- free toffee or taffy to put the pieces together.
Toffee gets hard as a rock and sticks things together (even teeth!).
The recipes are typically 2 cups sugar to 1 cup water, heat lots
(crack stage).

Looking these up made me want to make some with my 4 yr old...maybe.