Soft robots leverage deformable bodies to achieve different types of locomotion, improve transportability, and safely navigate cluttered environments. In this context, variable-stiffness structures provide soft robots with additional properties, such as the ability to increase forces transmitted to the environment, to lock into different body configurations, and to reduce the number of actuators required for morphological change. Tensegrity structures have been recently proposed as a biologically inspired design principle for soft robots. However, the few examples of tensegrity structures with variable stiffness displayed relatively small stiffness change (i.e., by a factor of 3) or resorted to multiple and bulky actuators. In this article, we describe a novel design approach to variable-stiffness tensegrity structures (VSTSs) that relies on the use of variable-stiffness cables (VSCs). As an example, we describe the design and implementation of a three-strut tensegrity structure with VSCs made of low melting point alloys. The resulting VSTS displays unprecedented stiffness changes by a factor of 28 in compression and 13 in bending. We show the capabilities of the proposed VSTS in three validation scenarios with different tensegrity architectures: (1) a beam with tunable load-bearing capability, (2) a structure that can self-deploy and lock its shape in both deployed and undeployed states, and (3) a joint with underactuated shape deformations.