It depends exactly what application you are looking for.
The amount of stress a material will tolerate is defined by its tensile strength and the amount it will deform under a given stress is defined by its Young's Modulus (low Young's Modulus is flexible high is stiff)
If you want something which will stretch by a large percentage of its original dimensions then rubbers (generally classified as elastomers) tend to be good. Typical applications include things like engine mountings and flexible covers for articulated joints. Rubbers also tend to be self-damping and so are good for vibration isolation.
In terms of maximum stress resistance then spring steels are widely used, these tend to be medium carbon, low alloy steels which are hardened and tempered. These materials have very good tensile strength and toughness. Although steel as a material has high stiffness, you can control the degree of flexibility of a spring by its shape (eg coil springs) or by mechanical linkages as in the case of torsion springs. Overall steel tends to be the preferred for high performance springs although you do see polymer and composite leaf springs eg in commercial vehicles.
Another option for some applications is polymer textiles and rope, for example the dynamic ropes used in climbing here the way that yarns are formed and woven also contribute to their flexibility. These tend to be used for impact absorption and are effective at moderating high impact loads without failing although they may be damaged by loads close to their ultimate capacity.