Sachverhalt:
A. Am 2. April 2008 wurden dem Schuldner, X._, die Zahlungsbefehle in den Betreibungen Nrn 1 bis 2 des Betreibungsamtes Y._ an dessen Wohnadresse, A._, B._, zugestellt. Da sich der Schuldner oftmals in C._ aufhält und auch zum Zeitpunkt der Zustellung nicht persönlich angetroffen werden konnte, wurden die Zahlungsbefehle von seiner Ehefrau, D._, entgegengenommen. Mit Eingabe vom 4. April 2008 erhob der Schuldner in den angegebenen Betreibungen Rechtsvorschlag, den er mit Schreiben vom 8. April 2008 an die schweizerische Botschaft in C._ zur Weiterleitung an das Betreibungsamt Y._ erneuerte. Überdies ersuchte er um gebührenfreie Bescheinigung der erhobenen Rechtsvorschläge, welchem Begehren das Betreibungsamt nicht nachkam.
B. Deswegen beschwerte sich der Schuldner am 25. Juli 2008 bei der Aufsichtsbehörde über das Betreibungs- und Konkursamt Basel-Stadt und ersuchte darum, das Betreibungsamt anzuweisen, ihm die erhobenen Rechtsvorschläge gebührenfrei zu bescheinigen und die Bescheinigung an seine Adresse in C._ zu senden. Mit Entscheid vom 30. April 2009 wies die Aufsichtsbehörde in teilweiser Gutheissung der Beschwerde das Betreibungsamt an, dem Schuldner die Bescheinigung der Rechtsvorschläge in den Betreibungen Nrn. 1 bis 2 gebührenfrei auszustellen, und wies im Übrigen die Beschwerde ab.
C. Der Schuldner gelangt mit einer als Beschwerde in Zivilsachen entgegengenommenen, am 28. Mai 2009 der Kanzlei zugegangenen Eingabe vom 20. Mai 2008 an das Bundesgericht. Er ersucht darum, das Urteil der Aufsichtsbehörde über das Betreibungs- und Konkursamt Basel-Stadt vom 30. April 2009 aufzuheben und das Betreibungsamt anzuweisen, die Rechtsvorschläge gegen die Betreibungen Nrn. 1 bis 2 zu bestätigen und die Bestätigung eingeschrieben an seine Adresse in Israel zuzustellen. Ferner seien das Betreibungsamt und die Aufsichtsbehörde anzuweisen, ohne Verzug zu handeln. Mit Eingabe vom 30. Juni 2009, die dem Bundesgericht am 3. Juli 2009 zugegangen ist, ersucht der Beschwerdeführer um unentgeltliche Rechtspflege und um Bestellung eines amtlichen Rechtsbeistands. Es sind keine Vernehmlassungen eingeholt worden.

Erwägungen:
1. Entscheide in Schuldbetreibungs- und Konkurssachen unterliegen der Beschwerde in Zivilsachen (<ref-law> i.V.m. <ref-law>). Beschwerdeentscheide der kantonalen Aufsichtsbehörden über Verfügungen der Vollstreckungsorgane gemäss <ref-law> sind Endentscheide im Sinn von <ref-law>, zumal diese Verfügungen im laufenden Vollstreckungsverfahren grundsätzlich nicht mehr infrage gestellt werden können (<ref-ruling> E. 1.2 S. 351).
2. 2.1 Der Beschwerdeführer macht zusammengefasst geltend, in <ref-law> sei die direkte "Zusendung von Betreibungen" usw. in das Ausland auf postalischem Weg ausdrücklich vorgesehen. Er habe seine Adresse in C._ dem Betreibungsamt mitgeteilt, womit der Zusendung der verlangten Bescheinigung gemäss <ref-law> durch die Post nichts im Wege stehe.
2.2 Wohnt der Schuldner im Ausland, so erfolgt die Zustellung durch die Vermittlung der dortigen Behörden oder, soweit völkerrechtliche Verträge dies vorsehen, oder wenn der Empfängerstaat zustimmt, durch die Post (<ref-law>). Nach den für das Bundesgericht verbindlichen tatsächlichen Feststellungen wohnt der Beschwerdeführer weiterhin an der A._ in B._, an welcher Adresse auch die Ehegattin des Beschwerdeführers und fünf seiner Kinder gemeldet sind. Das Obergericht schliesst aus diesen tatsächlichen Gegebenheiten in rechtlicher Hinsicht auf den Wohnsitz des Beschwerdeführers in B._, was der Beschwerdeführer weder hinsichtlich der tatsächlichen Feststellungen noch der rechtlichen Schlussfolgerung infrage stellt. Hat aber der Beschwerdeführer unangefochten Wohnsitz in der Schweiz, so kommt <ref-law> nicht zur Anwendung, setzt doch diese Bestimmung einen Wohnsitz des Betreibungsschuldners im Ausland voraus (YVAN JEANNERET/SAVERIO LEMBO, Commentaire romand, Poursuite et Faillite, 2005, N. 10 zu <ref-law>; PIERRE-ROBERT Gilliéron, Commentaire de la loi fédérale sur la poursuite pour dette et la faillite, 1999, N. 26 zu <ref-law>).
2.3 Soweit es um eine Mitteilung des Betreibungsamtes in der Schweiz geht, erfolgt diese durch eingeschriebenen Brief oder durch Übergabe gegen Empfangsbestätigung (<ref-law>) und zwar im konkreten Fall an die angegebene schweizerische Wohnadresse des Beschwerdeführers. Ist dagegen eine Betreibungsurkunde zuzustellen, so erfolgt dies nach den Bestimmungen der Art. 64 und 66 SchKG, wobei im konkreten Fall keine Zustellung von Betreibungsurkunden durch die Post ins Ausland erfolgt, da eine solche - wie bereits dargelegt, E. 2.2 - lediglich unter den in <ref-law> aufgezählten, hier nicht erfüllten Voraussetzungen erfolgen kann (in diesem Sinn: GILLIÉRON, a.a.O. N. 22 zu <ref-law>). Entgegen der in der Beschwerde vertretenen Auffassung kann der Beschwerdeführer somit nicht gestützt auf <ref-law> verlangen, dass ihm die Bestätigung der erhobenen Rechtsvorschläge per Post ins Ausland zugestellt wird. Eine Verletzung von Bundesrecht liegt nicht vor.
3. Der Beschwerdeführer wirft der Aufsichtsbehörde eine Verletzung des Beschleunigungsgebots vor und macht zur Begründung im Wesentlichen geltend, die Aufsichtsbehörde habe Anfang Oktober 2008 Kenntnis vom Umstand erhalten, dass das Betreibungsamt die Rechtsvorschlagsbescheinigung weder ins Ausland noch an die Schweizer Adresse zugestellt habe. Indem die Aufsichtsbehörde erst am 30. April 2009 entschieden habe, sei sie den Anforderungen an ein rasches Verfahren gemäss § 12 der Verfassung des Kantons Basel-Stadt bzw. gemäss der Bundesverfassung und der EMRK nicht nachgekommen. Mit diesen Ausführungen wirft der Beschwerdeführer der Aufsichtsbehörde vor, das Verfahren nicht innert angemessener Frist durchgeführt zu haben.
3.1 Soweit der Beschwerdeführer auf § 12 der kantonalen Verfassung verweist, legt er nicht dar, inwiefern ihm diese Bestimmung einen weitergehenden Rechtsschutz gewährt als <ref-law>. Sodann verlangt auch Art. 6 Ziff. 1 EMRK, soweit diese Bestimmung auf das vorliegende Verfahren überhaupt anwendbar ist, eine Entscheidung innert angemessener Frist, wobei diese Bestimmung mit Bezug auf die Verfahrensdauer in ihrem Gehalt nicht weiter geht als <ref-law> (<ref-ruling> E. 5.1 S. 332). Die Rüge des Beschwerdeführers ist somit allein im Lichte der Bundesverfassung zu prüfen.
3.2 Nach <ref-law> hat jede Person in Verfahren vor Gerichts- und Verwaltungsinstanzen Anspruch auf Beurteilung innert angemessener Frist. Eine Verletzung dieser Bestimmung ist gegeben, wenn die zuständige Verwaltungs- oder Gerichtsbehörde den verlangten Entscheid nicht binnen der Frist erlässt, welche nach der Natur der Sache und nach der Gesamtheit der übrigen Umstände als angemessen erscheint (<ref-ruling> E. 1.1 S. 409; <ref-ruling> E. 5.1 S. 331). Dabei sind insbesondere die Art des Verfahrens, die Schwierigkeit der Materie, das Verhalten der Beteiligten und auch die Bedeutung der Angelegenheit für den Rechtsuchenden zu berücksichtigen (<ref-ruling> E. 5.2 S. 332; <ref-ruling> E. 2a S. 191; <ref-ruling> E. 5b S. 325).
3.3 Aus dem Protokoll der Akten in der Sache ergibt sich, dass die Beschwerde in der Sache am 30. Juli 2008 bei der Aufsichtsbehörde eingegangen und am 31. Juli 2008 dem Betreibungsamt zur Stellungnahme zugestellt worden ist. Die betreffende Stellungnahme traf am 12. August 2008 ein und wurde am 3. September 2008 mit einer Frist von 14 Tagen zur Stellungnahme dem Beschwerdeführer zugestellt. Die Stellungnahme des Beschwerdeführers vom 5. Oktober 2008 ging am 16. Oktober 2008 bei der Aufsichtsbehörde ein. Am 1. Februar 2009 wurde diese Stellungnahme dem Betreibungsamt zugestellt und dieses um Mitteilung ersucht, ob die Bescheinigung über die rechtzeitig eingegangenen Rechtsvorschläge inzwischen dem Beschwerdeführer zugestellt worden sei, was das Betreibungsamt am 4. Februar 2009 verneinte. Schliesslich erging der Entscheid am 30. April 2009.
Die beanspruchte Dauer des Verfahrens liegt im Rahmen der Erfordernisse von <ref-law>. Insbesondere kann von der Aufsichtsbehörde nicht verlangt werden, dass sie sich ständig mit dem Fall des Beschwerdeführers befasst, sodass gewisse Verzögerungen im Verfahrensablauf durchaus normal sind und in Kauf genommen werden müssen (<ref-ruling> E. 5.2 S. 332). Entscheidende Bedeutung kommt aber im vorliegenden Fall dem Umstand zu, dass sich die Verfahrensdauer nicht auf hochrangige Rechtsgüter des Beschwerdeführers ausgewirkt hat. Dabei gilt es insbesondere in Betracht zu ziehen, dass der Beschwerdeführer zum Beweis des erhobenen Rechtsvorschlages nicht auf die Bescheinigung angewiesen ist, sondern den verlangten Beweis auch auf andere Weise erbringen kann (Balthasar BESSENICH, Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, SchKG I, 1998, N. 28 zu <ref-law>).
4. Nach dem Gesagten ist die Beschwerde abzuweisen. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig (<ref-law>).
5. Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege ist abzuweisen, da sich die Beschwerde als von Anfang an aussichtslos erwiesen hat (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und der Aufsichtsbehörde über das Betreibungs- und Konkursamt Basel-Stadt schriftlich mitgeteilt.
Lausanne, 31. Juli 2009
Im Namen der II. zivilrechtlichen Abteilung
des schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Zbinden