Come on out Charmander.

This shelter business really doesn't pay to your strengths. But find an area with a small hill face and use Dig to burrow into it creating a cave like structure. Now we're going to use Mud Slap to fling mud into the sides of the structure, the ceiling and the floor. Now finish with a mighty Flamethrower and strike all sides of the cave structure to burn the mud. Use that powerful flame of yours to burn the mud into a concrete like setting to finish the job.