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.

Erwägungen:
1. Vom Rückzug der Beschwerde durch den Beschwerdeführer 1 wird Kenntnis genommen.
2. Mit dem angefochtenen Urteil schützte das Verwaltungsgericht des Kantons Graubünden das Vorgehen der Baubehörde der Gemeinde Davos, welche das Projektänderungsgesuch der Beschwerdegegnerin im vereinfachten Verfahren geprüft und bewilligt hatte, womit sie dem Beschwerdeführer 2 im Verfahren um Bewilligung des Änderungsgesuchs keine Parteistellung einräumte und es ihm insbesondere verunmöglichte, Einsprache gegen die Projektänderung zu erheben. Das angefochtene Urteil ist ein letztinstanzlicher kantonaler Endentscheid in einer öffentlich-rechtlichen Angelegenheit (vgl. Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG). Zur Rüge, die Vorinstanz habe zu Unrecht seine Parteistellung im Verfahren vor der Baubehörde verneint, ist der Beschwerdeführer 2 im bundesgerichtlichen Verfahren nach <ref-law> berechtigt (<ref-ruling> E. 1.3 S. 270; <ref-ruling> E. 6.2 S. 198 f.). Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass. Auf die Beschwerde des Beschwerdeführers 2 ist vorbehältlich rechtsgenügender Rügen (Art. 42 Abs. 2 i.V.m. <ref-law>) einzutreten.
3. Der Beschwerdeführer 2 macht geltend, die Vorinstanz habe (teilweise) seine Eingaben nicht gelesen bzw. die von ihm vorgebrachten Argumente nicht geprüft. Er rügt damit (sinngemäss) eine Verletzung der Begründungspflicht, welche Bestandteil des Anspruchs auf rechtliches Gehör (<ref-law>) bildet. Diese Rüge erweist sich als unbegründet: Die grundsätzliche Pflicht der Behörde, ihren Entscheid zu begründen, bedeutet nicht, dass sie sich mit jeder tatbeständlichen Behauptung und jedem rechtlichen Einwand auseinandersetzen muss. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken. Der Bürger soll wissen, warum die Behörde entgegen seinem Antrag entschieden hat, damit er gegebenenfalls den Entscheid sachgerecht anfechten kann (<ref-ruling> E. 4.1; <ref-ruling> E. 3.1 S. 277; je mit Hinweisen). Diesen Anforderungen genügt der vorinstanzliche Entscheid.
4. Der Beschwerdeführer 2 rügt, das Projektänderungsgesuch sei nicht wie gemäss Art. 45 der Raumplanungsverordnung für den Kanton Graubünden vom 24. Mai 2005 (KRVO) vorgesehen öffentlich aufgelegt und im Amtsblatt publiziert worden. Die Baubehörde habe kein korrektes Bewilligungsverfahren durchgeführt, in welchem er Rechtsverletzungen hätte rügen können. Ihm sei keine Gelegenheit zur Stellungnahme gegeben worden. In die Bewilligung vom 1. April 2011 habe er erst nachträglich einsehen können. Damit seien sein Anspruch auf rechtliches Gehör sowie Art. 33 Abs. 3 lit. a RPG (SR 700) verletzt worden. Umstritten ist somit einerseits, ob die Baubehörde dem Beschwerdeführer 2 im Verfahren um Bewilligung des von der Beschwerdegegnerin eingereichten Projektänderungsgesuchs hätte Parteistellung einräumen und ihm die von <ref-law> garantierten Parteirechte hätte gewähren müssen und andererseits, ob sie das Projektänderungsgesuch hätte öffentlich auflegen sowie amtlich publizieren müssen.
4.1 Gemäss <ref-law> muss sich am Verfahren vor allen kantonalen Vorinstanzen als Partei beteiligen können, wer zur Beschwerde an das Bundesgericht berechtigt ist. Soweit einer Person nach <ref-law> gegen letztinstanzliche kantonale Entscheide die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen steht, haben die Kantone ihr im Verwaltungsverfahren Parteistellung zu gewähren. Im Anwendungsbereich des Raumplanungsgesetzes bestimmt überdies Art. 33 Abs. 3 lit. a RPG, dass die Legitimation für Rechtsmittel gegen Verfügungen mindestens im gleichen Umfang wie für die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht gewährleistet sein muss.
4.2 Zur Beschwerde in öffentlich-rechtlichen Angelegenheiten ist nach <ref-law> berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a), durch den angefochtenen Entscheid oder Erlass besonders berührt ist (lit. b) und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat (lit. c). Die Nähe der Beziehung zum Streitgegenstand muss bei Bauprojekten insbesondere in räumlicher Hinsicht gegeben sein. Ein schutzwürdiges Interesse liegt vor, wenn die tatsächliche oder rechtliche Situation des Beschwerdeführers durch den Ausgang des Verfahrens beeinflusst werden kann (<ref-ruling> E. 1.3 S. 413 mit Hinweisen). Die Voraussetzungen von <ref-law> hängen eng zusammen; insgesamt kann insoweit an die Grundsätze angeknüpft werden, die zur Legitimationspraxis bei der Verwaltungsgerichtsbeschwerde nach Art. 103 lit. a OG entwickelt worden sind (vgl. <ref-ruling> E. 2a S. 51 f., 379 E. 4b S. 386 f.).
Geht es wie vorliegend nicht um die Erteilung einer neuen Baubewilligung, sondern um nachträgliche Änderungen an einem bereits rechtskräftig bewilligten, aber noch nicht fertiggestellten Bauprojekt, ist - jedenfalls wenn es sich nur um Änderungen von untergeordneter Bedeutung handelt - für die Beschwerdeberechtigung nicht massgebend, ob die beschwerdeführende Person ein Interesse an der Verhinderung oder Anpassung des bewilligten Projekts hat. Beschwerdeberechtigt im Sinne von <ref-law> ist in einem solchen Fall nur, wer ein tatsächliches oder rechtliches Interesse daran hat, dass das Bauprojekt nicht abgeändert, sondern so wie zunächst bewilligt verwirklicht wird. Wer gegen ein solches Bauprojekt lediglich Einwände hat, die nicht unmittelbar mit der ersuchten Projektänderung im Zusammenhang stehen und die er bereits im Baubewilligungsverfahren vorgebracht hat oder hätte vorbringen können, ist im Verfahren um Bewilligung des Projektänderungsgesuchs nicht (mehr) beschwerdeberechtigt.
4.3 Die Vorinstanz hielt in tatsächlicher Hinsicht fest, die von der Beschwerdegegnerin ersuchte Projektänderung betreffe hauptsächlich das Erdgeschoss, wo gewisse Bauteile, die gemäss Baubewilligung vom 16. September 2008 erhalten bleiben sollten, nun abgebrochen würden. Dabei führten die Neubauteile zu einer neuen Raumeinteilung, nicht aber zu einer andersartigen Nutzung. Bei den bewilligten Änderungen handle es sich um geringfügige Anpassungen, die keinen Mehrverkehr verursachten, keine Erhöhung der Ausnützungsziffer zur Folge hätten und äusserlich nicht nennenswert in Erscheinung treten würden.
Der Beschwerdeführer 2 bringt zwar vor, das neue Baugesuch enthalte ein neu strukturiertes Bauvorhaben und es handle sich beim nun bewilligten um ein anderes Projekt, insbesondere nicht mehr um eine Kombination eines Altbaus mit einem Neubau. Damit vermag er indessen nicht darzutun und es ist auch nicht ersichtlich, inwiefern die tatsächlichen Feststellungen der Vorinstanz geradezu willkürlich sein sollten. In tatsächlicher Hinsicht ist deshalb auf die Feststellungen der Vorinstanz abzustellen (vgl. Art. 105 Abs. 1 und 2 i.V.m. <ref-law>).
4.4 Die Baubehörde bewilligte demnach ein Projekt, das vom ursprünglich geplanten Bauvorhaben nicht wesentlich abweicht. Die bewilligten Änderungen treten äusserlich nicht nennenswert in Erscheinung und haben keinen Einfluss auf die von der Baute ausgehenden Immissionen auf das Nachbargrundstück. Es genügt deshalb für die Bejahung seiner Beschwerdeberechtigung im Projektänderungsverfahren nicht, dass der Beschwerdeführer 2 Mitglied einer Stockwerkeigentümergemeinschaft auf einem benachbarten Grundstück ist. Der Beschwerdeführer 2 legt nicht dar und es ist nicht ersichtlich, inwiefern er ein tatsächliches oder rechtliches Interesse daran haben sollte, dass das Bauprojekt nicht abgeändert, sondern wie ursprünglich bewilligt verwirklicht wird. Er räumt denn auch selber ein, die Projektänderung sei für ihn im Vergleich zum bewilligten Projekt nicht nachteilig. Die Einwände, die er gegen das Projekt erhebt, stehen nicht mit der Projektänderung im Zusammenhang und wurden bereits im Baubewilligungs- und Einspracheverfahren und im daran anschliessenden Rechtsmittelverfahren vorgebracht bzw. hätten damals vorgebracht werden können. Auf sie ist im vorliegenden Verfahren nicht mehr einzugehen.
4.5 Soweit sich der Beschwerdeführer 2 sodann auf kantonales Recht beruft und geltend macht, nach Art. 45 KRVO hätte das Projektänderungsgesuch öffentlich aufgelegt und im Amtsblatt publiziert werden müssen, kann er daraus ebenfalls nichts zu seinen Gunsten ableiten. Das Bundesgericht überprüft die Auslegung und Anwendung des kantonalen Rechts nur auf Willkür hin und nur insofern, als eine solche Rüge in der Beschwerde vorbebracht und begründet worden ist (vgl. Art. 106 Abs. 2 i.V.m. <ref-law>). Art. 50 f. KRVO regelt das Meldeverfahren als vereinfachtes Baubewilligungsverfahren. Es findet gemäss Art. 50 Abs. 1 KRVO Anwendung auf untergeordnete Bauvorhaben, bei welchen mit keinen Einsprachen zu rechnen ist, wie insbesondere geringfügige Projektänderungen bereits bewilligter Bauvorhaben sowie bauliche Massnahmen, die nach aussen nicht in Erscheinung treten, zonenkonform sind und zu keinen Veränderungen bezüglich Verkehrsbelastung oder Ausnützung führen. Die Vorinstanz ist unter den gegebenen Umständen jedenfalls nicht in Willkür verfallen, wenn sie gestützt auf Art. 50 Abs. 1 KRVO zum Schluss gekommen ist, die ersuchte Projektänderung habe ohne öffentliche Auflage und amtliche Publikation im Meldeverfahren bewilligt werden dürfen (vgl. Urteil 1C_376/2011 vom 8. Februar 2012 E. 2.3).
4.6 Die Vorinstanz hat somit keine Rechtsverletzung im Sinne von <ref-law> begangen, indem sie das Vorgehen der Baubehörde schützte, das Projektänderungsgesuch der Beschwerdegegnerin im Meldeverfahren nach Art. 50 f. KRVO zu prüfen und zu bewilligen, ohne dem Beschwerdeführer 2 Parteistellung einzuräumen.
5. Nicht zu hören ist der Beschwerdeführer 2 schliesslich mit seiner Rüge, die Vorinstanz habe ein von ihm beantragtes Sachverständigengutachten hinsichtlich der Gestaltungsanforderungen an das Bauprojekt nicht eingeholt und damit seinen Anspruch auf rechtliches Gehör verletzt. Dies weil der Anspruch auf rechtliches Gehör (<ref-law>) direkt mit der Parteistellung verknüpft ist, die dem Beschwerdeführer im Verfahren um Bewilligung des Projektänderungsgesuchs nach dem Gesagten nicht eingeräumt werden musste.
6. Die Beschwerde des Beschwerdeführers 2 ist somit abzuweisen, soweit darauf einzutreten ist. Das Gesuch um aufschiebende Wirkung wird damit gegenstandslos. Bei diesem Ausgang des Verfahrens werden der Beschwerdeführer 1 sowie der Beschwerdeführer 2 kostenpflichtig (vgl. <ref-law>), wobei bei der Festsetzung der Gerichtskosten zu berücksichtigen ist, dass der bis zum Zeitpunkt des Rückzugs der Beschwerde des Beschwerdeführers 1 betriebene Aufwand des Bundesgerichts relativ gering ausgefallen ist. Die Beschwerdeführer haben der privaten Beschwerdegegnerin für das bundesgerichtliche Verfahren eine angemessene Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Vom Rückzug der Beschwerde des Beschwerdeführers 1 wird Kenntnis genommen.
2. Die Beschwerde des Beschwerdeführers 2 wird abgewiesen, soweit darauf einzutreten ist.
3. Dem Beschwerdeführer 1 werden Gerichtskosten in der Höhe von Fr. 500.-- auferlegt. Dem Beschwerdeführer 2 werden Gerichtskosten in der Höhe von Fr. 2'500.-- auferlegt.
4. Die Beschwerdeführer haben der privaten Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit eine Parteientschädigung von Fr. 3'000.-- zu bezahlen.
5. Die Stellungnahme des Beschwerdeführers 2 vom 5. März 2012 wird den übrigen Beteiligten und der Vorinstanz mit diesem Urteil zugestellt.
6. Dieses Urteil wird den Parteien, der Gemeinde Davos und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 22. März 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Mattle