Sachverhalt: A. Am 16. September 2008 erteilte die Baubehörde Davos der Z._ AG die Baubewilligung für den Teilabbruch und den Neubau eines Wohn- und Geschäftshauses auf der Parzelle Nr. 117 in Davos Platz. Gleichzeitig wies sie eine Einsprache der Stockwerkeigentümergemeinschaft W._ gegen das Bauprojekt ab. Die von der Stockwerkeigentümerschaft bzw. von einzelnen Stockwerkeigentümern gegen die Baubewilligung erhobenen Beschwerden wiesen das Verwaltungsgericht des Kantons Graubünden am 28. April 2009 sowie das Bundesgericht am 17. Februar 2010 (Urteil 1C_388/2009) ab. B. Im Zusammenhang mit den Abbrucharbeiten entstanden Bedenken bezüglich der Stabilität jener Gebäudeteile, deren Abbruch nicht geplant war. Weitere Untersuchungen ergaben, dass für diese Gebäudeteile tatsächlich ein Sicherheitsrisiko bestand. Aus diesem Grund stellte die Bauherrin am 15. März 2011 ein Gesuch um Abbruch und Neubau jener bisher vom Abbruch ausgesparten Gebäudeteile. Die Baubehörde prüfte das Projektänderungsgesuch im vereinfachten Verfahren und bewilligte es am 1. April 2011. Eine von X._ und Y._ dagegen erhobene Beschwerde wies das Verwaltungsgericht am 1. November 2011 ab. C. Gegen das Urteil des Verwaltungsgerichts haben X._ und Y._ am 7. Dezember 2011 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie haben beantragt, der angefochtene Entscheid sei aufzuheben und die Gemeinde Davos zu verpflichten, das am 15. März 2011 eingereichte Projektänderungsgesuch dem ordentlichen Baubewilligungsverfahren zu unterziehen, sodass die interessierte Nachbarschaft gegen das Baugesuch anhand der vollständigen Baugesuchsunterlagen noch Einsprache erheben könne. Als vorsorgliche Massnahme sei der Z._ AG einstweilen zu verbieten, ein sechstes Geschoss zu erstellen. D. Die Vorinstanz schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werde. Die Gemeinde Davos beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen. Die Z._ AG beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. E. Mit Eingabe vom 13. Februar 2012 hat X._ (nachfolgend Beschwerdeführer 1) erklärt, er ziehe seine Beschwerde vor Bundesgericht zurück. Y._ (nachfolgend Beschwerdeführer 2) hält mit Eingabe vom 5. März 2012 an der Beschwerde fest. 