Sachverhalt: Sachverhalt: A. Im Mai 2000 schloss der Fussballclub A._ (Club, Beschwerdeführer) als Arbeitgeber mit B._ (Beschwerdegegner) einen Arbeitsvertrag, in dem er B._ für die Zeit vom 1. Juli 2000 bis zum 30. Juni 2002 als Trainer (Manager) anstellte. In Art. 10 bestimmten die Parteien, dass Streitigkeiten aus diesem Vertrag oder dessen Beendigung von jeder der Parteien der FIFA unterbreitet werden könnten, deren Entscheid endgültig und bindend sein solle. Am 7. März 2001 entliess der Club den Trainer fristlos mit der Begründung, dieser habe bei Vertragsschluss verheimlicht, dass er an einer Krankheit leide. A.a Nach der Beendigung des Arbeitsvertrags reichte der Club beim 10. Zivilgericht erster Instanz in Istanbul Klage ein mit dem Begehren, die fristlose Kündigung als gültig zu erklären und den Arbeitnehmer zu verpflichten, USD 725'000.-- zurückzuzahlen. Das erstinstanzliche Gericht erkannte mit Entscheid vom 20. Mai 2003, der Club habe den Vertrag rechtsgültig beendet und verpflichtete den Arbeitnehmer zur Rückzahlung von USD 375'000.--. Die Appellation des Arbeitnehmers gegen diesen Entscheid ist hängig. A.b Am 26. März 2001, zehn Tage nach Einreichung der Klage des Clubs beim türkischen Zivilgericht, unterbreitete der Arbeitnehmer den Streitfall der FIFA-Spielerstatus-Kommission in der Schweiz. Er machte geltend, die fristlose Entlassung sei ungerechtfertigt, und verlangte die Bezahlung sämtlicher vereinbarter Beträge bis zum ordentlichen Vertragsende am 30. Juni 2002. Zusätzlich klagte er Schadenersatz in Höhe von USD 1'000'000 ein. Das Büro der Spielerstatus-Kommission hielt im Entscheid vom 26. März 2002 zwar dafür, die Vertragsbeendigung am 7. März 2001 sei gültig erfolgt, verpflichtete aber den Club zur Bezahlung von USD 764'000.--. Dieser Betrag entspricht den Lohnforderungen für Januar, Februar sowie anteilsmässig für März 2001 und umfasst ausserdem eine Entschädigung für die Vertragsbeendigung in Höhe von drei Monatslöhnen. A.c Der Entscheid des Büros der FIFA-Spielerstatus-Kommission wurde dem türkischen Fussballverband am 4. April 2002 per Fax zugestellt, der ihn seinerseits dem Club am 9. April 2002 per Fax weiterleitete. Mit Schreiben vom 19. April 2002 an den türkischen Fussballverband erklärte darauf der Club beim FIFA-Exekutivkomitee Appellation gegen diesen Entscheid. Das FIFA-Exekutivkomitee trat am 28. Juni 2003 auf das Rechtsmittel nicht ein mit der Begründung, die 20-tägige Frist sei nicht eingehalten worden. A.d Am 20. August 2003 gelangte der Club an das Schiedsgericht für Sport in Lausanne (Tribunal Arbitral du Sport: TAS). Er benannte X._ als Schiedsrichter und beantragte, die Vollstreckbarkeit des Entscheids der FIFA-Spielerstatus-Kommission sei bis zum Urteil des zuständigen Appellationsgerichts in Istanbul aufzuschieben; eventuell seien die Entscheide der Spielerstatus-Kommission und des FIFA-Exekutivkomitees aufzuheben; ausserdem sei festzustellen, dass der Club seinem ehemaligen Arbeitnehmer aus dem Arbeitsvertrag oder dessen Beendigung nichts schulde. Am 1. September 2003 bezeichnete der Beschwerdegegner als Schiedsrichter Y._, wobei er sich ausdrücklich vorbehielt, die Zuständigkeit des Schiedsgerichts für Sport zu bestreiten. In seiner detaillierten Rechtsschrift vom 8. September 2003 bestritt er die Zuständigkeit des Schiedsgerichts für Sport ausdrücklich und beantragte die Beschränkung des Verfahrens auf die Zuständigkeitsfrage. A.d Am 20. August 2003 gelangte der Club an das Schiedsgericht für Sport in Lausanne (Tribunal Arbitral du Sport: TAS). Er benannte X._ als Schiedsrichter und beantragte, die Vollstreckbarkeit des Entscheids der FIFA-Spielerstatus-Kommission sei bis zum Urteil des zuständigen Appellationsgerichts in Istanbul aufzuschieben; eventuell seien die Entscheide der Spielerstatus-Kommission und des FIFA-Exekutivkomitees aufzuheben; ausserdem sei festzustellen, dass der Club seinem ehemaligen Arbeitnehmer aus dem Arbeitsvertrag oder dessen Beendigung nichts schulde. Am 1. September 2003 bezeichnete der Beschwerdegegner als Schiedsrichter Y._, wobei er sich ausdrücklich vorbehielt, die Zuständigkeit des Schiedsgerichts für Sport zu bestreiten. In seiner detaillierten Rechtsschrift vom 8. September 2003 bestritt er die Zuständigkeit des Schiedsgerichts für Sport ausdrücklich und beantragte die Beschränkung des Verfahrens auf die Zuständigkeitsfrage. B. Mit "Zwischen"-Entscheid ("Preliminary Decision") vom 29. Oktober 2003 stellte das Schiedsgericht für Sport fest, dass es nicht zuständig sei, den Streit zwischen den Parteien zu entscheiden. Es trat daher auf das Schiedsbegehren vom 20. August 2003 betreffend die Appellation gegen den Entscheid des Exekutivkomitees vom 28. Juni 2003 und den Entscheid der Spielerstatus-Kommission vom 26. März 2002 nicht ein. Zur Begründung erwog das Schiedsgericht, das FIFA Zirkular Nr. 827 vom 11. November 2002, publiziert in der FIFA Medieninformation vom 12. Dezember 2002, habe keine konstitutive Wirkung und begründe daher auf keinen Fall die Zuständigkeit des TAS als letzte Appellationsinstanz für Streitigkeiten innerhalb der FIFA; vielmehr bedürfte es zur Begründung dieser Zuständigkeit einer Ergänzung der FIFA-Statuten. Ohne statutarische Grundlage der FIFA liesse sich die Zuständigkeit des TAS nach den Erwägungen des Schiedsgerichts nur auf die Schiedsklausel in einem Vertrag oder auf eine ad-hoc-Schiedsvereinbarung der Parteien stützen; daran fehlt es vorliegend nach den Feststellungen im Schiedsurteil. B. Mit "Zwischen"-Entscheid ("Preliminary Decision") vom 29. Oktober 2003 stellte das Schiedsgericht für Sport fest, dass es nicht zuständig sei, den Streit zwischen den Parteien zu entscheiden. Es trat daher auf das Schiedsbegehren vom 20. August 2003 betreffend die Appellation gegen den Entscheid des Exekutivkomitees vom 28. Juni 2003 und den Entscheid der Spielerstatus-Kommission vom 26. März 2002 nicht ein. Zur Begründung erwog das Schiedsgericht, das FIFA Zirkular Nr. 827 vom 11. November 2002, publiziert in der FIFA Medieninformation vom 12. Dezember 2002, habe keine konstitutive Wirkung und begründe daher auf keinen Fall die Zuständigkeit des TAS als letzte Appellationsinstanz für Streitigkeiten innerhalb der FIFA; vielmehr bedürfte es zur Begründung dieser Zuständigkeit einer Ergänzung der FIFA-Statuten. Ohne statutarische Grundlage der FIFA liesse sich die Zuständigkeit des TAS nach den Erwägungen des Schiedsgerichts nur auf die Schiedsklausel in einem Vertrag oder auf eine ad-hoc-Schiedsvereinbarung der Parteien stützen; daran fehlt es vorliegend nach den Feststellungen im Schiedsurteil. C. Mit staatsrechtlicher Beschwerde stellt der Club das Rechtsbegehren, der Entscheid des Schiedsgerichts für Sport vom 29. Oktober 2003 sei aufzuheben, die Zuständigkeit des TAS festzustellen und die Sache an diese Instanz zur neuen Entscheidung zurückzuweisen. Ausserdem stellt er den prozessualen Antrag, der Beschwerde sei aufschiebende Wirkung zu bewilligen. Der Beschwerdeführer beruft sich auf Art. 190 Abs. 2 lit. b IPRG und rügt, das TAS habe seine Zuständigkeit zu Unrecht verneint. Zur Begründung bringt er hauptsächlich vor, das TAS sei vom Exekutivkomitee der FIFA als Berufungsinstanz eingesetzt worden und zwar anstelle des in Art. 45 i.V.m. Art. 42 Abs. 1 lit. b, c der hier anwendbaren Reglementbestimmungen 2001 vorgesehenen Schiedsgerichts des Fussballs (TAF). Das TAS habe daher seine Zuständigkeit als Berufungsinstanz zu Unrecht verneint. Im Übrigen würde nach den Ausführungen des Beschwerdeführers auch die Schiedsvereinbarung im Arbeitsvertrag vom Mai 2000 die Zuständigkeit des Schiedsgerichts für Sport begründen; überdies verhalte sich der Beschwerdegegner rechtsmissbräuchlich, wenn er, der die FIFA angerufen habe, sich auf eine fehlende Schiedsklausel berufe, obwohl das Exekutivkomitee der FIFA seinem Entscheid eine Rechtsmittelbelehrung über die Anfechtung beim TAS angefügt habe. C. Mit staatsrechtlicher Beschwerde stellt der Club das Rechtsbegehren, der Entscheid des Schiedsgerichts für Sport vom 29. Oktober 2003 sei aufzuheben, die Zuständigkeit des TAS festzustellen und die Sache an diese Instanz zur neuen Entscheidung zurückzuweisen. Ausserdem stellt er den prozessualen Antrag, der Beschwerde sei aufschiebende Wirkung zu bewilligen. Der Beschwerdeführer beruft sich auf Art. 190 Abs. 2 lit. b IPRG und rügt, das TAS habe seine Zuständigkeit zu Unrecht verneint. Zur Begründung bringt er hauptsächlich vor, das TAS sei vom Exekutivkomitee der FIFA als Berufungsinstanz eingesetzt worden und zwar anstelle des in Art. 45 i.V.m. Art. 42 Abs. 1 lit. b, c der hier anwendbaren Reglementbestimmungen 2001 vorgesehenen Schiedsgerichts des Fussballs (TAF). Das TAS habe daher seine Zuständigkeit als Berufungsinstanz zu Unrecht verneint. Im Übrigen würde nach den Ausführungen des Beschwerdeführers auch die Schiedsvereinbarung im Arbeitsvertrag vom Mai 2000 die Zuständigkeit des Schiedsgerichts für Sport begründen; überdies verhalte sich der Beschwerdegegner rechtsmissbräuchlich, wenn er, der die FIFA angerufen habe, sich auf eine fehlende Schiedsklausel berufe, obwohl das Exekutivkomitee der FIFA seinem Entscheid eine Rechtsmittelbelehrung über die Anfechtung beim TAS angefügt habe. D. Der Beschwerdegegner beantragt in seiner innert erstreckter Frist eingereichten Vernehmlassung die Abweisung der Beschwerde. Das TAS hat nach Ablauf der verfügten Frist eine Vernehmlassung eingereicht.