But then if we say we are cold we say Мне холодно which must be an Adjective as their is no verb
.
Consider the Past and Future tenses:
Мне было холодно.
Мне будет холодно.

There is a verb there. We just leave it out in the Present.
Мне холодно.
"To me is cold", so to speak.