Sachverhalt:
A. Das Kreisgericht VIII Bern-Laupen verurteilte Y._ am 3. Dezember 2007 wegen Totschlags, begangen am 1. Juli 2005 zum Nachteil von A._, zu einer Freiheitsstrafe von 7 Jahren.
B. Das Obergericht des Kantons Bern sprach Y._ am 29. August 2008 auf Appellation des Prokurators 4 der Staatsanwaltschaft III Bern-Mittelland der vorsätzlichen Tötung schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von 10 Jahren.
C. Gegen dieses Urteil erhebt der Generalprokurator des Kantons Bern Beschwerde in Strafsachen an das Bundesgericht. Er beantragt, das Urteil des Obergerichts des Kantons Bern vom 29. August 2008 aufzuheben. Y._ sei des Mordes schuldig zu sprechen und mit 14 Jahren Zuchthaus zu bestrafen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
D. Das Obergericht des Kantons Bern reichte eine Vernehmlassung ein, worin es unter anderem auf seine Erwägungen im angefochtenen Urteil verweist. In seiner Vernehmlassung beantragt Y._, auf die Beschwerde sei nicht einzutreten. Eventualiter sei sie abzuweisen. Überdies ersucht er um unentgeltliche Rechtspflege und Verbeiständung.

Erwägungen:
1. 1.1 Der Beschwerdeführer rügt, die Sachverhaltsfeststellung der Vorinstanz zum Tatmotiv und Eskalationsgrund (als Tatauslöser) sei willkürlich. Dabei habe diese bei ihrer Beweiswürdigung den Grundsatz "in dubio pro reo" verletzt, indem sie zu Unrecht Zweifel zugunsten des Angeklagten an seinem Tatmotiv angenommen habe. Es seien zwei mögliche Tatmotive, Geld bzw. Verrat, in Betracht gezogen worden. Die Vorinstanz habe zutreffenderweise die Version, wonach der Beschwerdegegner sein Opfer aufgrund eines Verrats getötet habe, verworfen. Dann habe sie schrittweise und schlüssig die Zweifel der ersten Instanz an einem finanziellen Motiv ausgeräumt und die Spannungen zwischen Täter und Opfer am Tatabend unmissverständlich auf das Thema Geld zurückgeführt. Im Ergebnis habe sie dennoch und ohne nähere Begründung das Motiv "Geld" ausgeschlossen bzw. das Tatmotiv in widersprüchlicher Weise offen gelassen, obwohl daneben kein anderes Motiv mehr im Raum gestanden habe. Sie habe die Tat einem schweren Aggressionsausbruch des Beschwerdegegners bzw. einer Provokation des Opfers zugeschrieben, was keine Stütze in den Akten finde. Eine Provokation des Opfers bzw. eine Affekthandlung des Beschwerdegegners sei eine reine Mutmassung und stehe im Widerspruch zu den Zeugenaussagen und dem Spurenbild. Dadurch sei die Vorinstanz in Willkür verfallen.
1.2 Der Beschwerdegegner führt in der Vernehmlassung aus, es sei möglich, dass weitere Motive hinter dem Tötungsdelikt standen. Die Vorinstanz habe detailliert begründet, weshalb sie das Tatmotiv offen lasse. Die Argumente des Beschwerdeführers reichten nicht aus, um Willkür zu begründen.
1.2 Der Beschwerdegegner führt in der Vernehmlassung aus, es sei möglich, dass weitere Motive hinter dem Tötungsdelikt standen. Die Vorinstanz habe detailliert begründet, weshalb sie das Tatmotiv offen lasse. Die Argumente des Beschwerdeführers reichten nicht aus, um Willkür zu begründen.
1.3 1.3.1 Gestützt auf die unbestrittenen Feststellungen der Vorinstanz, die teilweise auf den von der ersten Instanz festgestellten Sachverhalt verweist, schoss der Beschwerdegegner am Abend des 1. Juli 2005 viermal auf seine Bekannte und Landsfrau A._ in ihrem Wohnhaus. Zuvor hatte er mit ihr zusammen das Nachtessen eingenommen und den Hund spazieren geführt. Die Schussabgabe erfolgte im Wohnzimmer, wo sich der Beschwerdegegner und das Opfer auf den Sofas gegenüber sassen. Zwei Schüsse trafen das Opfer in die unteren Extremitäten, der dritte Schuss drang in die Brust ein. Beim vierten Schuss handelt es sich um einen praktisch aufgesetzten Kopfschuss. Das Opfer verblutete.
1.3.2 Eingangs der Beweiswürdigung führt die Vorinstanz zur Frage des Tatmotivs aus, das Aussageverhalten des Beschwerdegegners sei widersprüchlich, zum Teil sogar geradezu absurd. Stellenweise habe er schlicht gelogen. Seine Aussagen seien insgesamt als wenig glaubhaft einzustufen.
Die Pistole habe der Beschwerdegegner am Tatabend per Zufall mit sich geführt, weil ihn das Opfer gebeten habe, eine Waffe zu besorgen. Er habe die Tat nicht geplant und keine Erfahrung im Umgang mit Waffen gehabt.
Der Beschwerdegegner habe sich nur mittels Privatdarlehen finanziell über Wasser gehalten, welche er in seinem Bekanntenkreis aufgenommen hatte. Seine finanzielle Situation habe zur Tatzeit wesentlich schlechter ausgesehen, als er darstelle. Er habe mit seinem Restaurant keinen Gewinn erzielt und sei mit deutlich über Fr. 100'000.-- verschuldet gewesen. Sein Umgang mit Geld sei unbekümmert gewesen, insbesondere weil er das Restaurant trotz erheblicher Schulden habe umbauen wollen. Das Opfer habe ihm ein Darlehen über Fr. 30'000.-- gewährt, welches er am 30. Juni 2005, einen Tag vor dem Tatabend, mit einem Zins von Fr. 5'000.-- hätte zurückzahlen sollen. Bis zum Tatzeitpunkt sei keine Darlehensrückzahlung erfolgt. Das Thema Geld habe am Tatabend eine Rolle gespielt, und es sei dabei zu erheblichen Spannungen gekommen. Das Opfer werde von Zeugen als soziale, einfühlsame und kompetente Persönlichkeit und Berufsfrau beschrieben, andererseits aber auch als dominant und herrschsüchtig. Seine direkte und verletzende Art habe schon öfters zu Differenzen Anlass gegeben.
Für die vom Beschwerdegegner vorgebrachte Version, wonach das Opfer ihn und seine Familie an den iranischen Geheimdienst verraten habe bzw. zwei unbekannte Männer am Tatabend in der Wohnung des Opfers anwesend waren, gebe es keine Anhaltspunkte. Entgegen den Ausführungen des Beschwerdegegners habe das Opfer auch keine Reise in den Iran bzw. andere Bemühungen unternommen, um der Schwester des Beschwerdegegners einen Reisepass zu beschaffen.
Die Vorinstanz schliesst einen Unfall am Tatabend aufgrund der viermaligen Schussabgabe aus, weil jeder Schuss ein Treffer war. Sie erwägt, es sei unklar, was sich unmittelbar vor der Schussabgabe zugetragen habe. Jedenfalls habe der Beschwerdegegner vier gezielte Schüsse auf das Opfer abgegeben. Gestützt auf die Zeugenaussagen der Nachbarn und des Spurenbildes, wonach das Opfer dem Täter gegenüber sass, bestehe kein Hinweis, dass es sich bedroht gefühlt habe oder dass es zu einem länger dauernden heftigen Streit gekommen sei. Die Schussabgabe sei nur mit einer heftigen Gefühlswallung von Wut und Zorn auf Seiten des Beschwerdegegners erklärbar, welche das Opfer durch eine erhebliche Kränkung oder eine äusserst starke Provokation unmittelbar vor der Tat ausgelöst habe. Worin diese Provokation bestanden habe, sei unbekannt, ebenso das Tatmotiv. Das zur Rückzahlung fällige Darlehen habe am Tatabend mit grosser Wahrscheinlichkeit zu einer akuten Verstimmung zwischen dem Beschwerdegegner und seinem Opfer geführt. Der Umgang des Beschwerdegegners mit Geld sei locker gewesen. Deshalb sei davon auszugehen, dass die Forderung nach einer Rückzahlung des Darlehens alleine nicht ausgereicht habe, um eine derartige Reaktion zu veranlassen. Das Motiv könne nicht eindeutig geklärt werden, die Tat stehe vermutlich zumindest mittelbar vor dem Hintergrund des fälligen Darlehens. Im Zweifel sei zugunsten des Beschwerdegegners von der günstigsten Variante auszugehen. Danach sei sein Tatmotiv offen und es sei ihm ein schwerer Aggressionsausbruch, also ein Affektdelikt zuzuschreiben.
1.3.3 In ihrer Vernehmlassung führt die Vorinstanz im Wesentlichen aus, es lasse sich nicht rechtsgenüglich beweisen, dass Geld das Motiv für die Tat gewesen sei. Es sei aber falsch zu behaupten, dass nur zwei Motive für die Tötung in Frage kämen, so dass das eine erwiesen sei, wenn das andere wegfalle.
1.4 Gemäss dem in <ref-law> und Art. 6 Ziff. 1 EMRK verankerten Grundsatz "in dubio pro reo" darf sich der Richter nicht von der Existenz eines für den Angeklagten ungünstigen Sachverhalts überzeugt erklären, wenn bei objektiver Betrachtung erhebliche und nicht zu unterdrückende Zweifel bestehen, dass sich der Sachverhalt so verwirklicht hat (<ref-ruling> E. 2a S. 41 mit Hinweisen). Der Richter darf auch nicht zu Unrecht Zweifel zugunsten des Angeklagten annehmen (Urteil 6B_351/2008 E. 3.1). Ob dieser Grundsatz verletzt ist, prüft das Bundesgericht nur unter dem Gesichtspunkt der Willkür (<ref-ruling> E. 2.a S. 41 mit Hinweisen). Nach der bundesgerichtlichen Praxis liegt Willkür in der Beweiswürdigung nach <ref-law> vor, wenn der angefochtene Entscheid auf einer schlechterdings unhaltbaren oder widersprüchlichen Beweiswürdigung beruht bzw. im Ergebnis offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Für die Annahme von Willkür genügt es nicht, wenn eine andere Lösung auch als vertretbar oder sogar zutreffender erscheint (<ref-ruling> E. 1.2 S. 177; <ref-ruling> E. 3.1 S. 473 f., je mit Hinweisen). Soweit der Beschwerdeführer im Rahmen der Beweiswürdigung den Grundsatz "in dubio pro reo" im Sinne von <ref-law> und Art. 6 Ziff. 1 EMRK als verletzt rügt, fällt sein Vorbringen mit der Willkürrüge nach <ref-law> zusammen.
1.4 Gemäss dem in <ref-law> und Art. 6 Ziff. 1 EMRK verankerten Grundsatz "in dubio pro reo" darf sich der Richter nicht von der Existenz eines für den Angeklagten ungünstigen Sachverhalts überzeugt erklären, wenn bei objektiver Betrachtung erhebliche und nicht zu unterdrückende Zweifel bestehen, dass sich der Sachverhalt so verwirklicht hat (<ref-ruling> E. 2a S. 41 mit Hinweisen). Der Richter darf auch nicht zu Unrecht Zweifel zugunsten des Angeklagten annehmen (Urteil 6B_351/2008 E. 3.1). Ob dieser Grundsatz verletzt ist, prüft das Bundesgericht nur unter dem Gesichtspunkt der Willkür (<ref-ruling> E. 2.a S. 41 mit Hinweisen). Nach der bundesgerichtlichen Praxis liegt Willkür in der Beweiswürdigung nach <ref-law> vor, wenn der angefochtene Entscheid auf einer schlechterdings unhaltbaren oder widersprüchlichen Beweiswürdigung beruht bzw. im Ergebnis offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Für die Annahme von Willkür genügt es nicht, wenn eine andere Lösung auch als vertretbar oder sogar zutreffender erscheint (<ref-ruling> E. 1.2 S. 177; <ref-ruling> E. 3.1 S. 473 f., je mit Hinweisen). Soweit der Beschwerdeführer im Rahmen der Beweiswürdigung den Grundsatz "in dubio pro reo" im Sinne von <ref-law> und Art. 6 Ziff. 1 EMRK als verletzt rügt, fällt sein Vorbringen mit der Willkürrüge nach <ref-law> zusammen.
1.5 1.5.1 Die Vorinstanz legt die zur Diskussion stehenden Tatmotive anhand der persönlichen Situation von Täter und Opfer im Tatzeitpunkt ausführlich dar. Sie zieht politische (Verrat an den iranischen Geheimdienst) und finanzielle Motive sowie eine Gemütsbewegung aufgrund eines Streits in Betracht. Gestützt auf eine umfangreiche und sorgfältige Beweiswürdigung verwirft sie die ersten beiden Gründe. Die Vorinstanz lässt das Tatmotiv im Ergebnis offen, weil der Beschwerdegegner keine glaubhaften Aussagen zum Grund für die Tat sowie zu deren Ablauf gemacht habe und Augenzeugen fehlen würden. Dennoch geht sie davon aus, Opfer und Täter hätten sich aufgrund des fälligen Darlehens gestritten. Dabei habe das Opfer den Beschwerdegegner äusserst stark provoziert. Dies habe zu einem Aggressionsausbruch des Beschwerdegegners geführt. Er habe die Tat im Affekt, in einer heftigen Gefühlswallung aus Wut und Zorn begangen.
1.5.2 Zwar würdigt die Vorinstanz die möglichen Tatmotive detailliert, im Ergebnis verfällt sie aber in Spekulationen über den wahren Grund für die Tat und präsentiert mehrere mögliche Lösungen. Einerseits lässt sie im Endergebnis das Tatmotiv offen. Andererseits nennt sie innerhalb der Urteilsbegründung als Anlass für die Tat einen Streit, bei welchem Geld mittelbar eine Rolle gespielt hat. Dabei müsse das Opfer den Beschwerdegegner massgeblich provoziert haben, worauf er es im Affekt erschossen habe.
Die von der Vorinstanz in der Urteilsbegründung genannten Möglichkeiten können nicht gleichzeitig zutreffen, sie sind widersprüchlich. Das Tatmotiv ist entweder unklar, oder es ist bestimmbar. Indem die Vorinstanz zugleich in der Urteilsbegründung mit dem Streit wegen des Geldes bzw. der Provokation durch das Opfer mögliche Tatmotive angibt, aber im Ergebnis das Tatmotiv offen lässt, leidet der Entscheid an einem unauflösbaren Widerspruch. Willkür ist auch gegeben, wenn der angefochtene Entscheid in sich widersprüchlich ist, wobei sich der Widerspruch aus der Begründung ergeben kann (<ref-ruling> E. 5f. S. 29, 106 Ia 337 E. 2 S. 339 ; <ref-ruling> E. 1 S. 27; RtiD 2007 I 93 E. 5.4 S. 100 f.; je mit Hinweisen). Der angefochtene Entscheid ist willkürlich.
1.5.3 Dazu kommt, dass der nicht geständige Beschwerdegegner aus Sicht der Vorinstanz kein glaubhaftes Motiv für die Tat genannt hat. Sein Beweggrund stellt eine innere Tatsache dar, die sich durch die Tathandlung nach aussen manifestiert hat. Bei nicht geständigen Tätern ist das Motiv nur anhand äusserlicher Gegebenheiten zu ergründen. Politische und finanzielle Motive, welche sich aus der persönlichen Situation des Beschwerdegegners ergeben, hat die Vorinstanz verworfen. Den genauen Tatablauf hat sie mangels Augenzeugen und infolge der unglaubhaften Aussagen des einzigen Tatbeteiligten, des Beschwerdegegners, nicht rekonstruieren können. Dass ein Aggressionsausbruch infolge eines Streits bzw. eine Provokation Anlass der Tat war, ist eine reine Mutmassung der Vorinstanz. Diesbezüglich ist den Akten nichts Wesentliches zu entnehmen. Insbesondere haben die als Zeugen befragten Nachbarn keinen Streit wahrgenommen. Das Opfer sass im Zeitpunkt des ersten Schusses noch auf dem Sofa und erhob sich erst danach. Indem die Vorinstanz Annahmen zum Sachverhaltsablauf (Streit) und zum Motiv (Provokation des Opfers) trifft, welche keine wesentliche Stütze in den Akten finden, verfällt sie in Willkür. Die Charaktereigenschaften des Opfers, welches autoritär und verletzend sein konnte, sowie die Tatsache, dass es vor der Tat Probleme mit seinem Partner hatte, können für sich allein nicht Auslöser der Tat sein. Die Rüge des Beschwerdeführers erweist sich als begründet, weshalb die Beschwerde gutzuheissen ist.
2. 2.1 Der Beschwerdeführer macht geltend, die Vorinstanz verletze Bundesrecht, indem sie den Beschwerdegegner lediglich wegen vorsätzlicher Tötung nach <ref-law> anstelle von Mord nach Art. 112 i.V.m. <ref-law> verurteilt.
2.2 Wer vorsätzlich einen Menschen tötet, ohne dass eine der besonderen Voraussetzungen nach Art. 112 bis <ref-law> erfüllt ist, macht sich der vorsätzlichen Tötung strafbar (<ref-law>). Handelt der Täter besonders skrupellos, sind namentlich sein Beweggrund, der Zweck der Tat oder die Art der Ausführung besonders verwerflich so ist der Tatbestand des Mordes nach <ref-law> gegeben. Ob die Qualifikation des Mordes vorliegt, ist anhand einer Gesamtwürdigung der inneren und äusseren Umstände der Tat zu beurteilen (<ref-ruling> E. 1a S. 14 mit Hinweisen). Vorliegend wird die Sache zur Sachverhaltsergänzung bezüglich des Tatmotives an die Vorinstanz zurückgewiesen. Ohne die zur Subsumtion notwendigen tatsächlichen Grundlagen lässt sich die Bundesrechtskonformität der Verurteilung wegen vorsätzlicher Tötung nach <ref-law> nicht überprüfen (vgl. <ref-ruling> E. 3.4.3 S. 296). Diese Frage hat demnach offen zu bleiben. Die Vorinstanz hat die rechtliche Qualifikation der Tat erneut zu beurteilen, nachdem sie die Frage des Tatmotivs beantwortet hat.
3. Der Beschwerdegegner stellt ein Gesuch um unentgeltliche Rechtspflege. Er ist bedürftig, da er gemäss den vorinstanzlichen Feststellungen über erhebliche Schulden verfügt und sich im vorzeitigen Strafvollzug befindet. Sein Gesuch ist gutzuheissen. Es sind keine Gerichtskosten zu erheben, und sein Rechtsvertreter ist in üblichem Umfang aus der Bundesgerichtskasse zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Obergerichtes des Kantons Bern vom 29. August 2008 aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2. Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege wird gutgeheissen.
3. Es werden keine Gerichtskosten erhoben.
4. Dem Vertreter des Beschwerdegegners, Fürsprecher Dino Degiorgi, Bern, wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 3'000.-- ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, 1. Strafkammer, schriftlich mitgeteilt.
Lausanne, 20. Oktober 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Koch