Learn Russian: Почему с улицы дует холодный ветер? - Why is a cold wind blowing from the street?

To say you are going "from" somewhere, Russian pairs из with places that take в (in/to), and с with places that take на (on/to). Since you say на улицу (onto the street) and на улице (on the street), you must use с улицы to say "from the street".

What case is улицы, and why?

It is in the Genitive case. When the preposition с is used to mean "from" or "off of", it always forces the noun into the Genitive case. The dictionary form is улица, which changes to улицы here. Note that when с means "with", it takes the Instrumental case instead!

Could I change the word order to "Почему холодный ветер дует с улицы?"?

Yes, that is grammatically correct and perfectly understandable. However, Russian often places the verb before the subject in descriptions of nature, weather, or existence (like дует ветер or идёт дождь). Introducing the action before the subject sounds very natural here.

Could we use Зачем instead of Почему for "why" in this sentence?

No. Почему asks for the cause of an event (why is this happening?), whereas зачем asks for the purpose (for what goal or reason?). Since the wind doesn't blow with a specific conscious goal, почему is the only correct choice.