Sachverhalt:
A. Der Einzelrichter des Kantonsgerichts von Appenzell A.Rh. als Arrestrichter befahl am 2. September 2003 dem Betreibungsamt Appenzeller Vorderland, für den Gläubiger X._ "sämtliche Erbansprüche von Y._ [Schuldner] gegenüber der Erbengemeinschaft Z._ sel., verstorben am 14. Juli 2003 in A._" zu verarrestieren (Arrestbefehl Nr. ...). Am 22. September 2003 vollzog das Betreibungsamt den Arrest wie befohlen (Arresturkunde vom 25. September 2003). Gegen den Zahlungsbefehl in der von X._ eingeleiteten (Arrestprosequierungs-) Betreibung Nr. ... erhob Y._ (Teil-) Rechtsvorschlag nur in Bezug auf die Zinsen der in Betreibung gesetzten Forderung von Fr. 50'000.--. Am 5. November 2003 stellte X._ das Fortsetzungsbegehren. In der Folge vollzog das Betreibungsamt am 16. Dezember 2003 die Pfändung, indem es den Lohn von Y._ pfändete, indessen keine pfändbare Lohnquote feststellen konnte und einen provisorischen Verlustschein erliess (Pfändungsurkunde vom 20. Januar 2004).
B. Gegen die Pfändungsurkunde vom 20. Januar 2004 erhob X._ Beschwerde und verlangte die Pfändung der Erbansprüche von Y._. Mit Entscheid vom 23. März 2004 hiess das Obergericht von Appenzell A.Rh. als Aufsichtsbehörde für Schuldbetreibung und Konkurs die Beschwerde teilweise gut; sie hob die angefochtene Pfändungsurkunde auf und wies das Betreibungsamt an, eine neue Pfändungsurkunde "im Sinne der Erwägungen" auszufertigen (Dispositiv-Ziffer 1).
C. X._ hat den Beschluss der kantonalen Aufsichtsbehörde mit Beschwerdeschrift vom 10. Mai 2004 (rechtzeitig) an die Schuldbetreibungs- und Konkurskammer des Bundesgerichts weitergezogen und beantragt, der angefochtene Entscheid sei aufzuheben und das Betreibungsamt sei anzuweisen, die Erbansprüche von Y._ zu pfänden.
Die Aufsichtsbehörde hat anlässlich der Aktenüberweisung auf Gegenbemerkungen (Art. 80 OG) verzichtet. Der Betreibungsschuldner Y._ beantragt die Abweisung der Beschwerde. Zugleich stellt er das Gesuch um unentgeltliche Rechtspflege. Das Betreibungsamt hat auf eine Stellungnahme verzichtet.

Die Kammer zieht in Erwägung:
1. Die obere Aufsichtsbehörde hat die Pfändungsurkunde vom 20. Januar 2004 (über den Pfändungsvollzug vom 16. Dezember 2003) aufgehoben und das Betreibungsamt im Urteilsdispositiv angewiesen, eine neue Pfändungsurkunde "im Sinne der Erwägungen" auszufertigen. Aus den Urteilserwägungen Ziff. 7 a-c geht hervor, dass das Betreibungsamt die Pfändungsurkunde "in Anwendung von <ref-law>" auszufertigen habe, "der Arrest ins Leere" falle, kein Pfändungssubstrat vorhanden sei und das Einkommen des Beschwerdegegners nicht zu pfänden sei. Indem die Aufsichtsbehörde das Betreibungsamt angewiesen hat, eine leere Pfändungsurkunde (als Verlustschein nach <ref-law>) auszustellen, hat sie nicht bloss einen verfahrensleitenden Entscheid getroffen, sondern eine Massnahme im Vollstreckungsverfahren angeordnet, die Gegenstand einer Beschwerde gemäss <ref-law> sein kann (<ref-ruling> E. 1 S. 94). Der Beschwerdeführer verlangt - wie bereits vor der Aufsichtsbehörde - die Pfändung der Erbansprüche des Beschwerdegegners gegenüber der Erbmasse Z._ selig. Die Beschwerde ist insoweit zulässig.
2. Die Aufsichtsbehörde hat festgehalten, es könne offen gelassen werden, ob der Arrest überhaupt rechtzeitig mit Einleitung der Betreibung gemäss <ref-law> prosequiert worden sei, d.h. ob überhaupt ein Arrestbeschlag bestehe. Das Begehren um Fortsetzung der Betreibung nach <ref-law> sei wohl verfrüht gestellt worden; dies habe indessen keine Nichtigkeit der Pfändung zur Folge. Allerdings sei "der Arrest ins Leere gefallen" und kein Pfändungssubstrat vorhanden. Dabei hat die Aufsichtsbehörde auf den Erbteilungsvertrag vom 18. November 2003 verwiesen, welcher der Beschwerdegegner mit seinen Miterben abgeschlossen hat. Daraus geht hervor, dass dem Beschwerdegegner ein Erbteil von Fr. 13'976.-- zugewiesen wird und die Miterbin W._ für diese Forderung Verrechnung mit einer Forderung aus einem Darlehen erklärt, so dass der Beschwerdegegner aus der Erbteilung nichts erhält.
Der Beschwerdeführer hält demgegenüber fest, dass er den Arrest mit Betreibungsbegehren vom 2. Oktober 2003 rechtzeitig prosequiert habe und das Betreibungsamt beim Pfändungsvollzug nicht auf den Erbvertrag hätte abstellen dürfen. Er macht im Wesentlichen geltend, der Beschwerdegegner habe zu Unrecht über den verarrestierten Liquidationsanspruch an der Erbschaft verfügt und der Erbteilungsvertrag sei ohne Wirkung, ebenso die Verrechnungserklärung der Miterbin. Von fehlendem pfändbarem Arrestsubstrat und einer leeren Pfändung könne nicht gesprochen werden, da dem Beschwerdegegner aus dem Erbvertrag Fr. 13'976.-- zugeteilt würden und ihm vermutlich noch mehr zustehe.
2.1 Die Aufsichtsbehörde hat zunächst festgehalten, dass das Betreibungsamt dem Fortsetzungsbegehren vom 5. November 2003 nicht hätte Folge leisten dürfen, weil dieses frühestens am 14. November 2003 hätte gestellt werden können. Sie hat indessen die Nichtigkeit der Pfändung, auf welche sich der Beschwerdegegner berufen hatte, verneint. Diese Auffassung ist nicht zu beanstanden. Eine Verletzung von Vorschriften im Sinne von <ref-law> steht nicht in Rede. Anders als im Fall der Pfändung, die von einem örtlich unzuständigen Betreibungsamt vorgenommen wird und daher nichtig ist (<ref-ruling> E. 1 S. 61; <ref-ruling> E. 3 S. 49), können sich Dritte beim zuständigen Betreibungsamt über das Bestehen einer Pfändung erkundigen. Wenn einem verfrühten und daher fehlerhaften Fortsetzungsbegehren Folge geleistet wird, können die Gläubiger Beschwerde führen (Jent-Sørensen, in: Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, N. 22 zu <ref-law>; vgl. ferner Art. 9 Abs. 3 der Verordnung über die im Betreibungs- und Konkursverfahren zu verwendenden Formulare und Register sowie die Rechnungsführung [SR 281.31] betreffend Begehren, die höchstens zwei Tage zu früh einlangen). Der Hinweis des Beschwerdegegners, die Pfändung sei nichtig, geht daher fehl.
2.2 Nach den Sachverhaltsfeststellungen der Vorinstanz (Art. 63 Abs. 2 i.V.m. Art. 81 OG) hat das Betreibungsamt den Erbanteil des Beschwerdegegners am 22. September 2003 verarrestiert. Sodann haben der Beschwerdegegner und seine Miterben mit Vertrag vom 18. November 2003 ihre Erbschaft offenbar geteilt. Zur Zeit des Arrestvollzuges hat also die Erbengemeinschaft noch bestanden.
2.2.1 Für die Verarrestierung des Erbanteils ist die Verordnung des Bundesgerichts vom 17. Januar 1923 über die Pfändung und Verwertung von Anteilen an Gemeinschaftsvermögen (SR 281.41, VVAG) massgebend (<ref-ruling> E. 2c S. 66). Wäre es zulässig, dass die Erben trotz Verarrestierung des Erbanteils selbständig und auch für die Gläubiger des betriebenen Miterben verbindlich teilen könnten, wären sie damit ohne weiteres in der Lage, die Behörde gemäss <ref-law> auszuschalten und damit den Schutzzweck, welcher deren Mitwirkung für die Gläubiger haben soll, zu vereiteln (Bisang, Die Zwangsverwertung von Anteilen an Gesamthandschaften, Diss. Zürich 1978, S. 135). Dies wollen Art. 6 und Art. 12 VVAG verhüten. Nach der Rechtsprechung können denn auch weder der Schuldner persönlich, noch an seiner Stelle das Betreibungsamt mit verbindlicher Wirkung für die Gläubiger der Teilung zustimmen (BGE 61 III 160 S. 163 betreffend Erbteilung nach Verarrestierung des Erbanteils; BGE 71 III 99 E. 2 S. 103 ). Wollen die Erben schon vor dem Verwertungsstadium von sich aus zur Teilung schreiten, so haben sie dies dem Betreibungsamt zu melden, welches an die zuständige Behörde zu gelangen hat, damit diese mitwirke (Urteil des Bundesgerichts vom 6. November 1947, E. 1, BlSchK 1948 S. 153).
2.2.2 Im vorliegenden Fall hat die zuständige Behörde unbestrittenermassen an der Erbteilung nicht mitgewirkt. Ist aber die nach dem Arrest ohne Mitwirkung der Behörde vorgenommene Teilung für die Gläubiger nicht bindend (vgl. Tuor/Picenoni, Berner Kommentar, N. 8 u. 14 zu <ref-law>), kann sie auch nicht bewirken, dass der Erbteil aus dem Arrest fällt (Bisang, a.a.O.). Bestreiten der Schuldner oder die Miterben, dass dem Schuldner aus der nach dem Arrest vollzogenen Erbteilung etwas zustehe, so bleibt nach der Rechtsprechung als Arrestsubstrat der nun als bestritten geltende Liquidationsanteil (BGE 61 III 160 S. 162 f.; <ref-ruling> E. 1 S. 108 betreffend Erbteilung nach Pfändung des Erbanteils), m.a.W. der Erbanteil existiert als Arrestsubstrat weiter und kann gepfändet werden (für das weitere Vorgehen vgl. BGE 61 III 95). Die Betreibungsbehörden sind nicht zuständig für die Beurteilung materiell-rechtlicher Fragen und dürfen daher nicht über die Höhe eines Anteils am Gemeinschaftsvermögen oder andere Einwendungen des Schuldners oder beteiligter Drittpersonen entscheiden (BGE 61 III 160 S. 162; <ref-ruling> E. 1 S. 108; <ref-ruling> E. 3b S. 42). Der Beschwerdeführer rügt daher zu Recht, dass sich die Aufsichtsbehörde darüber ausgesprochen hat, ob dem Beschwerdegegner aus dem Erbteilungsvertrag etwas zustehe. Wenn die Aufsichtsbehörde vor diesem Hintergrund zum Ergebnis gelangt ist, es gebe kein Arrestsubstrat, das nach wirksamer Fortsetzung der Arrestprosequierungsbetreibung mit Pfändung beschlagen werden könne, und angenommen hat, es könne offen bleiben, ob ein Arrestbeschlag am Erbanteil überhaupt bestehe, verletzt dies Bundesrecht.
2.3 Nach dem Dargelegten erweist sich die rechtzeitige Einleitung der Prosequierungsbetreibung, mithin das Bestehen des Arrestbeschlages (<ref-law>; <ref-ruling> E. 2 S. 93) als rechtlich erhebliche Tatsache, welche von der Aufsichtsbehörde zu Unrecht nicht von Amtes wegen erhoben worden ist (vgl. <ref-law>). Der angefochtene Entscheid ist daher in Gutheissung der Beschwerde aufzuheben, und die Sache ist an die Vorinstanz zur Erhebung des rechtserheblichen Sachverhaltes (Feststellung der Rechtzeitigkeit der Einleitung der Prosequierungsbetreibung) und zu neuer Entscheidung zurückzuweisen (Art. 64 Abs. 1 i.V.m. Art. 81 OG). Erweist sich die Einleitung der Arrestprosequierungsbetreibung als rechtzeitig, besteht der bestrittene Liquidationsanteil des Beschwerdegegners an der Erbschaft als Arrestsubstrat, welcher mit Pfändung beschlagen werden kann.
2.4 Der Beschwerdeführer rügt schliesslich nicht (Art. 79 Abs. 1 OG), dass die Aufsichtsbehörde angeordnet hat, das Einkommen des Beschwerdegegners sei nicht zu pfänden; insoweit erübrigen sich weitere Ausführungen zum angefochtenen Entscheid. Soweit der Beschwerdeführer dem Beschwerdegegner strafbares Handeln vorwirft und sich auf die Anfechtbarkeit von Rechtsgeschäften nach <ref-law> beruft, kann auf die Vorbringen nicht eingetreten werden, da im betreibungsrechtlichen Beschwerdeverfahren weder das eine noch das andere beurteilt werden kann (vgl. <ref-law>).
3. Das Beschwerdeverfahren ist grundsätzlich kostenlos (<ref-law>), und es darf keine Parteientschädigung zugesprochen werden (<ref-law>). Das Gesuch des Beschwerdegegners um Befreiung von Gerichtskosten ist gegenstandslos. Seinem Gesuch um Gewährung eines unentgeltlichen Rechtsbeistandes kann nicht entsprochen werden, da sein Rechtsbegehren (Abweisung der Beschwerde) als von vornherein aussichtslos bezeichnet werden muss (Art. 152 OG; <ref-ruling> E. 3 S. 393).

Demnach erkennt die Kammer:
1. Die Beschwerde wird, soweit darauf einzutreten ist, gutgeheissen, und Dispositiv-Ziffer 1 des Entscheides des Obergerichts von Appenzell A.Rh. als Aufsichtsbehörde für Schuldbetreibung und Konkurs vom 23. März 2004 wird aufgehoben. Die Sache wird im Sinne der Erwägungen zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Das Gesuch des Beschwerdegegners um Gewährung eines unentgeltlichen Rechtsbeistandes wird abgewiesen.
3. Dieses Urteil wird dem Beschwerdeführer, dem Beschwerdegegner, dem Betreibungsamt Appenzeller Vorderland und dem Obergericht von Appenzell A.Rh. als Aufsichtsbehörde für Schuldbetreibung und Konkurs schriftlich mitgeteilt.
Lausanne, 26. August 2004
Im Namen der Schuldbetreibungs- und Konkurskammer
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber: