Gabriel:
There are a number of midrashim that tie Gabriel to fire:
Devarim Rabbah 5:12:
"...He imposes peace in His heights." Said Reish Lakish, Michael is entirely snow and Gabriel is entirely fire, and they stand one beside the other and do not harm one another."
Bamidbar Rabbah 12:8:
"..."Dominion and dread etc" - the dominion, this is Michael and he is of snow, and the dread, this is Gabriel and he is of fire..."
Shir Hashirim Rabbah 3:11:
"Dashing to and fro [among] the creatures was something that looked like flares" and this one doesn't put out that one and that one doesn't put out this one. Michael the lord of snow and Gabriel the lord of fire and this one doesn't put out that one and that one doesn't put out this one."
Midrash Tehillim 117:4:
"...said to Him Gabriel: I am the lord of fire; I shall go and heat him up from the outside and cool him down on the inside and I shall make a miracle within a miracle..."
and from the Zohar 1:16a:4:
"...And Gabriel, the Prince of His Left, Fire..."
and 3:225a:11:
"...And Gabriel who is the fire of intellect..."
and there are many more kabbalistic or semi-kabbalistic sources that state the same.
Michael:
As mentioned by @solsdottir and in the midrashim I brought about Gabriel, Michael was often connected to snow. However, there are other sources that connect him to water:
Zohar 1:16a:4:
"..."He makes peace in His heights". We learn that Michael, the Prince of the Right Side of Hashem, water and hail."
and 3:225a:11:
""...and Michael who is the waters of intellect..."
Divrei Nagidim on the Hagaddah, Magid, Arami Oved Avi:
"...and it is written: "your prince, Michael"...and these two angels, Michael of water...and He raised Michael from water..."
Chiddushei Aggadot on tractate Berachot 4b:
"Michael etc. The essence of Michael is water, on the right and in charge of grace..."
Sefer Habahir 11:
"..."He imposes peace in His heights" - comes to teach that Michael is the lord of the Right of The Holy One, Blessed Is He [and is of] water and hail..."
Kli Yakar on Genesis 28:12:
"...and as infers the Recanati, Uriel lord of air, Michael lord of water, Raphael lord of earth and Gabriel lord of fire..."
and there are many more kabbalistic or semi-kabbalistic sources that state the same.
Other angels:
The Kli Yakar source brought above paraphrases the Recanati who stated that Uriel is related to air and Raphael to earth.
This is likely based on this Zohar:
"...Uriel, who is air. Meaning the wind (or spirit) of intellect. With Raphael, who is ashes, meaning the dirt of intellect..."
This same idea is brought several times by Shnei Luchot Habrit, for example, here.
Note: Other than the Zohar 1:16a:4, all the sources were translated into English by myself.