Sachverhalt:
A. Das Strafgericht des Kantons Basel-Stadt sprach X._ am 8. November 2002 der Hehlerei, der Urkundenfälschung, der mehrfachen qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz sowie der Widerhandlung gegen das Waffengesetz schuldig und verurteilte ihn zu einer zweijährigen Gefängnisstrafe und zu einer Busse von Fr. 500.--. Von der Anklage der vorsätzlichen Tötung sprach es X._ frei.
Auf Appellation von X._ hin bestätigte das Appellationsgericht des Kantons Basel-Stadt am 24. März 2004 das erstinstanzliche Urteil.
B. X._ erhebt eidgenössische Nichtigkeitsbeschwerde beim Bundesgericht mit dem Antrag, der angefochtene Entscheid sei aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
C. Sowohl das Appellationsgericht als auch die Staatsanwaltschaft des Kantons Basel-Stadt ersuchen um Abweisung der Beschwerde.
D. Der Präsident des Kassationshofs hat der Beschwerde mit Verfügung vom 1. September 2004 die aufschiebende Wirkung erteilt.

Das Bundesgericht zieht in Erwägung:
1. Der Beschwerdeführer rügt <ref-law> als verletzt. Der von ihm gefälschte Fahrzeugausweis habe blossen Entwurfscharakter und sei nicht zur Verwendung bestimmt gewesen. Die Vorinstanz hätte die Herstellung dieser Urkunde deshalb als unvollendeten Versuch oder straflose Vorbereitungshandlung qualifizieren müssen.
1.1 Der Urkundenfälschung nach <ref-law> macht sich unter anderem schuldig, wer in der Absicht, sich einen unrechtmässigen Vorteil zu verschaffen, eine Urkunde fälscht oder verfälscht. Fälschen oder Verfälschen ist Herstellen einer unechten Urkunde (<ref-ruling> E. 2, mit Hinweisen). Das Delikt ist bereits mit der Herstellung der Urkunde vollendet; dass der Täter die Urkunde darüber hinaus auch gebraucht, ist nicht notwendig (Markus Boog, Basler Kommentar zum Strafrecht, Strafgesetzbuch II, Art. 251 N. 98; Günther Stratenwerth, Schweizerisches Strafrecht, Besonderer Teil II, Straftaten gegen die Gemeininteressen, 5. Aufl., Bern 2002, S. 134 N. 21).
1.2 Unbestritten ist, dass der Beschwerdeführer einen unechten Fahrzeugausweis betreffend den Personenwagen der Marke BMW 530i herstellte. Er fertigte die fragliche Urkunde nach eigenen Angaben im Hinblick auf einen geplanten Fahrzeugtransfer nach Jugoslawien an, um eventuellen Schwierigkeiten mit den dortigen Behörden, namentlich der Polizei, vorzubeugen. Denn dort würde sehr hart mit Leuten verfahren, die nicht auf sie zugelassene Fahrzeuge lenkten (kantonale Akten, S. 1174). Daraus ergibt sich ohne weiteres, dass der Beschwerdeführer ein unechtes Dokument herstellte, um sich einen unrechtmässigen Vorteil zu verschaffen (vgl. etwa BGE 74 IV 56). Damit hat er, wie die Vorinstanz zu Recht erkannte, den Tatbestand der Urkundenfälschung erfüllt. Dass er die Urkunde nicht verwendet haben will, tut nichts zur Sache, zumal das Delikt bereits im Zeitpunkt der Herstellung des Dokuments vollendet war. Entgegen seiner Ansicht kann deshalb nicht davon gesprochen werden, dass er lediglich zum Versuch angesetzt und eine bloss straflose Vorbereitungshandlung vorgenommen hat. Die Rüge erweist sich als nicht stichhaltig.
2. Der Beschwerdeführer wendet sich gegen den Schuldspruch der Hehlerei. Aufgrund des als Konsumgüterleasing zu qualifizierenden Geschäfts sei das Eigentum am Personenwagen BMW 530i auf den Leasingnehmer übergegangen. Eine Veruntreuung von dessen Seite falle daher ausser Betracht. Da es mithin an einem strafbaren Vermögensdelikt als Vortat fehle, könne er selbst nicht wegen Hehlens bestraft werden.
2.1 Der Hehlerei nach <ref-law> macht sich unter anderem schuldig, wer eine fremde Sache, von der er weiss oder annehmen muss, dass sie ein anderer durch eine strafbare Handlung gegen das Vermögen erlangt hat, verheimlicht oder veräussern hilft. Der Grund der Strafbarkeit des Hehlers liegt darin, dass er einen durch die Vortat geschaffenen rechtswidrigen Zustand fortsetzt und festigt. Er hindert oder erschwert damit die Wiederherstellung des durch die Vortat gestörten rechtmässigen Zustandes, beispielsweise die Wiedererlangung der Sache durch den Berechtigten (<ref-ruling> E. 1b; <ref-ruling> E. 2-3, je mit Hinweisen). Als Vortat der Hehlerei kommen insbesondere die Vermögensdelikte im formellen Sinne in Betracht, sofern sie eine Vermögensverschiebung bewirken (vgl. <ref-ruling> E. 2a-b, mit Hinweisen). Zu nennen ist im vorliegenden Zusammenhang namentlich die Veruntreuung gemäss <ref-law>. Nach diesem Tatbestand wird mit Zuchthaus bis zu fünf Jahren oder Gefängnis bestraft, wer sich eine ihm anvertraute fremde bewegliche Sache aneignet, um sich oder einen andern damit unrechtmässig zu bereichern. Ob eine Sache im Sinne der genannten Bestimmung fremd ist, beurteilt sich dabei nach zivilrechtlichen Kriterien (<ref-ruling> E. 3c/aa).
2.2 Entscheidend für die Frage der Eigentumsverhältnisse ist demnach der zwischen den Parteien abgeschlossene Vertrag (<ref-ruling> E. 6c, mit Hinweis auf den Entscheid des Bundesgerichts vom 31. August 1987, Str.284/1987, in SJ 1988, S. 145, 149; vgl. auch Entscheid des Bundesgerichts vom 22. März 2002, 6S.619/2001 E. 7a). Die Vorinstanz gelangte gestützt auf eine Würdigung mehrerer Umstände zum Schluss, dass die Parteien beim fraglichen Leasinggeschäft keine Veräusserungsabsicht gehabt haben. Gestützt auf diese verbindliche Feststellung (Art. 277bis Abs. 1 BStP) ging sie weiter davon aus, dass der fragliche BMW 530i im Eigentum der Leasinggeberin verblieben ist. Dies ist nicht zu beanstanden, zumal keine Anhaltspunkte für irgendeine nachträgliche abweichende Vereinbarung vorliegen. Die Vorinstanz war unter diesen Umständen nicht gehalten, noch die Vertragsurkunde beizuziehen. Ferner ist es entgegen der Ansicht des Beschwerdeführers auch bei einem Konsumleasing-Geschäft ohne weiteres möglich, dass der Gegenstand im Eigentum der Leasinggeberin verbleibt. Schliesslich geht aus dem angefochtenen Entscheid nicht hervor, dass die Vorinstanz von einem verkappten Abzahlungsvertrag ausgegangen ist, welcher aus formellen Gründen nichtig wäre. Ist somit die Leasinggeberin Eigentümerin geblieben, war dem Leasingnehmer der Personenwagen BMW 530i als fremde Sache "bloss" anvertraut (vgl. Marcel Alexander Niggli/ Christof Riedo, Basler Kommentar zum Strafrecht, Strafgesetzbuch II, Art. 138 N. 19). Mit der Weitergabe des Fahrzeugs an unberechtigte Dritte hat er die objektiven Merkmale von <ref-law> erfüllt (vgl. <ref-ruling> E. 2; <ref-ruling> E. 2). Da mithin von einem Vermögensdelikt als strafbarer Vortat auszugehen ist, geht die Kritik des Beschwerdeführers an der Sache vorbei.
3. Der Beschwerdeführer macht eine Verletzung von Art. 100 und <ref-law> geltend. Obschon Zweifel an seiner Zurechnungsfähigkeit bestünden, sei kein psychiatrisches Gutachten eingeholt worden.
3.1 Handelt es sich beim Täter um einen jungen Erwachsenen, zieht der Richter, soweit erforderlich, Gutachten über dessen körperlichen und geistigen Zustand ein (Art. 100 Abs. 1 und 2 StGB). Bestehen Zweifel an dessen Zurechnungsfähigkeit, ist eine Untersuchung im Sinne von <ref-law> anzuordnen. Der Richter soll dabei seine Zweifel nicht selber - etwa mit Hilfe psychiatrischer Fachliteratur - beseitigen, sondern hat vielmehr einen Sachverständigen beizuziehen. <ref-law> gilt nicht nur, wenn der Richter tatsächlich Zweifel an der Zurechnungsfähigkeit des Täters hegt, sondern auch, wenn er nach den Umständen des Falles Zweifel haben sollte (<ref-ruling> E. 2a). Solche Zweifel können sich etwa ergeben, wenn ein Widerspruch zwischen Tat und Täterpersönlichkeit besteht, ein völlig unübliches Verhalten vorliegt, wenn der Täter in ärztlicher Behandlung stand oder steht, die Tatausführung auffällige Eigenheiten zeigt oder die Tat mit der bisherigen Lebensführung unvereinbar erscheint (<ref-ruling> E. 4a; Entscheid des Bundesgerichts vom 27. April 2004, 6S.211/2003 E. 1.1).
3.2 Nach den verbindlichen Feststellungen der Vorinstanz waren beim Beschwerdeführer keinerlei Auffälligkeiten weder im Zusammenhang mit den Tatbegehungen noch im persönlichen Lebensbereich ersichtlich (vgl. auch Urteil des Strafgerichts des Kantons Basel-Stadt, S. 23 und 24). Bei dieser Sachlage musste die Vorinstanz keine ernsthaften Zweifel an dessen Zurechnungsfähigkeit im Sinne von <ref-law> haben. Denn das Verhalten des Beschwerdeführers war in Bezug auf das Geschehen vor, während und nach den von ihm verübten Straftaten überlegt, nachvollziehbar und realitätsbezogen. Vor diesem Hintergrund ist für die Frage der Zurechnungsfähigkeit daher nicht relevant, dass der Beschwerdeführer offenbar aufgrund eines psychiatrischen Gutachtens aus der Rekrutenschule ausgeschieden ist. Ebenso wenig ist in dieser Hinsicht von Belang, dass er nach seiner Flucht aus der Schweiz - wegen der in Notwehr begangenen Tötung - psychiatrische Hilfe in Belgrad in Anspruch genommen hat (kantonale Akten, S. 1172). Die Vorinstanz musste mithin keine Begutachtung des Beschwerdeführers anordnen. Dessen Rüge erweist sich als unbegründet.
4. Die Nichtigkeitsbeschwerde ist demnach abzuweisen.
Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens (Art. 278 Abs. 1 BStP).

Demnach erkennt das Bundesgericht:
1. Die Nichtigkeitsbeschwerde wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, der Staatsanwaltschaft des Kantons Basel-Stadt und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 10. Januar 2005
Im Namen des Kassationshofes
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: