Der Keller stellt einen Zubehörraum dar, für den keine Miete bezahlt wird. Demnach kann aufgrund eines feuchten Kellers keine Miete gemindert werden.
Zu dem Baugerüst, normalerweise könntest du die Miete nach § 536 BGB angemessen mindern. In deinem Fall finde ich es jedoch problematisch, da dir bereits vor Einzug die Baumaßnahme mitgeteilt wurde. Das heißt, du konntest in dem Fall abwägen, ob du die Baumaßnahme hinnimmst oder ob du dir eine andere Wohnung suchst. Meiner Meinung nach verwirkst du dadurch dein Mietminderungsrecht.
Treppenhaus, der Vermieter ist verkehrssicherungspflichtig. Das heißt, er hat dafür Sorge zu tragen, dass seine Mieter die Mietsache vertragsgemäß und gefahrlos gebrauchen können. Dazu gehört unter anderem, dass das Treppenhaus gefahrlos betreten werden kann. Hier solltet ihr den Mangel anzeigen, Frist setzen und auf die Dringlichkeit hinweisen und androhen, dass ihr eine Fachfirma mit der Reinigung beauftragt. Zur Mietminderung, hier kommt es wieder darauf an, ob der Mangel bereits zum Zeitpunkt des Einzuges bestand. Falls nicht, dann könnte man die Miete mindern, wobei die Minderung nicht viel mehr als 5 % betragen sollte.