Is it possible for a crystal to have different structures at different temperatures?

The microstructure of an alloy depends on such variables as the alloying elements present, their concentrations, and the heat treatment of the alloy (i.e., the temperature, the heating time at temperature, and the rate of cooling to room temperature). -Materials Science and Engineering: An Introduction 9th, Wiley, Calister, Rethwisch

Look up phase diagrams for different alloys

Here is a phase diagram for iron and carbon (steel). Depending on the composition of the alloy and the temperature it is at different crystal structures will form and multiple phases can be present at the same time. $\alpha$ is ferrite and has BCC structure, austenite ($\gamma$) has FCC.

Yes, it is very possible. Even water goes through such different structures

Two lines in particular from the wikipedia article on Ice:

• Ice II A rhombohedral crystalline form with highly ordered structure. Formed from ice Ih by compressing it at temperature of 190–210 K. When heated, it undergoes transformation to ice III.
• Ice III A tetragonal crystalline ice, formed by cooling water down to 250 K at 300 MPa. Least dense of the high-pressure phases. Denser than water.

No alloy is required. Plutonium is an example: