Sachverhalt: A. Vom 25. bis 31. Januar 2001 fand in Davos das Weltwirtschaftsforum (World Economic Forum, WEF) statt. Parallel dazu führten verschiedene Nicht-Regierungs-Organisationen in Davos unter dem Titel "The Public Eye on Davos" eine unabhängige internationale Konferenz durch, welche öffentlich war und ohne Anmeldung besucht werden konnte. Im Vorfeld des WEF waren mehrfach Störungen und Aktionen sowie die Durchführung einer nicht bewilligten Demonstration am 27. Januar 2001 in Davos angekündigt worden. Die Kantonspolizei traf daher zum Schutze des WEF, seiner Gäste, der Bevölkerung und der Infrastrukturanlagen zahlreiche Massnahmen und sicherte die Zufahrtswege nach Davos grossräumig mit verdichteten Personen- und Fahrzeugkontrollen (vgl. zu den Hintergründen BGE 127 I 164 und 128 I 167). B. Der als freier Journalist tätige K._ versuchte am 27. Januar 2001, mit dem Postauto von Chur über die Lenzerheide nach Davos zu gelangen. Bei "Crappa Naira" zwischen Brienz und Alvaneu wurde das Postauto angehalten; die Insassen wurden kontrolliert und an der Weiterreise nach Davos gehindert. Trotz Vorzeigens seines Presseausweises und seiner Angaben über journalistische Tätigkeiten am "Public Eye on Davos" wurde auch K._ von der Polizei zur Rückkehr nach Chur angehalten. Gegen diese Anordnung der Kantonspolizei Graubünden erhob K._ am 26. Februar 2001 beim Justiz-, Polizei- und Sanitätsdepartement des Kantons Graubünden Beschwerde. Er verlangte im Wesentlichen, dass die ihn betreffende Anordnung der Polizei und die ihr zugrunde liegende Allgemeinverfügung (Polizeieinsatz-Befehl) aufgehoben würden und überdies festgestellt werde, dass er in seinen verfassungsmässigen Rechten (Bewegungs-, Presse-, Meinungs- und Informationsfreiheit) verletzt worden sei. Mit Verfügung vom 13. Juli 2001 trat das Justiz-, Polizei- und Sanitätsdepartement auf die Beschwerde nicht ein und lehnte ein aufsichtsrechtliches Einschreiten gegen die Kantonspolizei ab. Es führte aus, die gerügten polizeilichen Massnahmen stellten tatsächliches Verwaltungshandeln und Realakte dar, gegen welche eine Beschwerde trotz allfälliger Beeinträchtigungen von Grundrechten nicht zulässig sei. Der den Polizeihandlungen zugrunde liegenden Einsatz-Befehl könne ebenfalls nicht angefochten werden. Schliesslich falle ein aufsichtsrechtliches Einschreiten ausser Betracht. C. K._ erhob in der Folge beim Verwaltungsgericht des Kantons Graubünden Rekurs. Mit Urteil vom 26. April 2002 trat dieses auf den Rekurs nicht ein und überwies ihn zur Behandlung an die Regierung des Kantons Graubünden. Die Regierung wies darauf die gegen die Verfügung des Justiz-, Polizei- und Sanitätsdepartements vom 13. Juli 2001 gerichtete Beschwerde mit Entscheid vom 29. April 2003 ab. Sie führte aus, die beanstandeten polizeilichen Handlungen und insbesondere die Rückweisung von K._ stellten sog. Realakte dar, gegen welche Beschwerden nach dem kantonalen Verfahrensrecht grundsätzlich ausgeschlossen seien. Das Departement habe diesen Grundsatz indessen zu absolut ausgelegt. Ausgehend von Art. 13 EMRK sei in gewissen Fällen auch bei verfügungsfreiem Handeln in Anlehnung an bestehende Verfahren Rechtsschutz zu gewähren. Ein solcher könne von einem Verwaltungsorgan gewährleistet werden und habe in analoger Anwendung der Regeln über die Anfechtung von Verfügungen zu erfolgen. Die Regierung nahm indessen gestützt auf das allgemeine kantonale Verwaltungsverfahrensrecht an, die Frist zur Beschwerde an das Departement sei nicht eingehalten worden. Dennoch prüfte sie die Beschwerde materiell und erachtete sie unter dem Gesichtswinkel der EMRK-Garantien als unbegründet. D. Gegen diesen Regierungsentscheid gelangte K._ erneut an das Verwaltungsgericht. Dieses ist mit Urteil vom 4. November 2003 auf den Rekurs nicht eingetreten. Das Gericht ging in der Begründung vom Gesetz über die Verwaltungsgerichtsbarkeit aus, wonach Entscheide der Regierung auf dem Gebiete des Staats- und Verwaltungsrechts an das Verwaltungsgericht weitergezogen werden können, wenn nach übergeordnetem Recht und nach Art. 6 Ziff. 1 EMRK eine letztinstanzliche Beurteilung durch ein kantonales Gericht erforderlich ist. Im vorliegenden Fall sei K._ indessen durch die beanstandeten polizeilichen Massnahmen nicht in zivilrechtlichen Ansprüchen gemäss Art. 6 Ziff. 1 EMRK betroffen und könne daher unter diesem Titel keinen gerichtlichen Rechtsschutz verlangen. Ein solcher Anspruch könne er auch nicht aus dem allgemeinen Rechtsstaatsprinzip und dem (noch nicht in Kraft gesetzten) Art. 29a BV ableiten. Art. 13 EMRK verleihe schliesslich lediglich einen Anspruch auf eine wirksame Beschwerde bei einem hinreichend unabhängigen verwaltungsinternen Rechtspflegeorgan. Diesen Anforderungen genüge der Entscheid der Regierung vom 29. April 2003. E. Gegen dieses Urteil des Verwaltungsgerichts hat K._ beim Bundesgericht am 6. Januar 2004 staatsrechtliche Beschwerde erhoben. Er stellt den Antrag, das Urteil des Verwaltungsgerichts sei aufzuheben und dieses sei anzuweisen, seinen Rekurs materiell zu behandeln. Er macht geltend, der Bundesverfassung sei ein Anspruch auf einen effektiven gerichtlichen Rechtsschutz zu entnehmen. Der Zugang zu einem Gericht ergebe sich ferner aus Art. 6 Ziff. 1 EMRK. Diese Bestimmung erfasse weite Teile des Verwaltungsrechts und komme immer zur Anwendung, wenn individuelle Freiheiten und Rechtsansprüche in Frage stehen. Die beanstandeten polizeilichen Massnahmen hätten ihn in seinen civil rights betroffen und ihm die Berufsausübung als Journalist und Berichterstatter verunmöglicht. Die Überprüfung durch die Regierung stelle keinen wahren Rechtsschutz dar. Der Nichteintretensentscheid des Verwaltungsgerichts verletze daher seinen Anspruch auf Zugang zu einem Gericht. Die Regierung und das Verwaltungsgericht beantragen unter Hinweis auf den angefochtenen Entscheid und die Akten die Abweisung der Beschwerde. 