Sachverhalt:
A. Das Kreisgericht V Burgdorf-Fraubrunnen verurteilte X._ am 13. Dezember 2007 wegen vorsätzlicher Tötung, Diebstahls und Versuchs dazu sowie Widerhandlungen gegen das Betäubungsmittelgesetz und das ANAG zu einer Freiheitsstrafe von 12 Jahren und einer Busse von 300 Franken.
X._ appellierte gegen dieses Urteil ans Obergericht des Kantons Bern mit dem Antrag, ihn vom Vorwurf der vorsätzlichen Tötung freizusprechen und ihn wegen vorsätzlicher schwerer Körperverletzung und fahrlässiger Tötung zu verurteilen. Die weiteren Schuldsprüche beanstandete er nicht und beantragte, ihn zu einer Freiheitsstrafe von 5 Jahren zu verurteilen.
Der Prokurator der Staatsanwaltschaft Emmental-Oberaargau erklärte ebenfalls Appellation. Diese wurde von der Generalprokuratur in eine Anschlussappellation umgewandelt. Sie beantragte, es sei festzustellen, dass die unangefochten gebliebenen Schuldsprüche in Rechtskraft erwachsen seien. X._ sei zusätzlich der vorsätzlichen Tötung schuldig zu sprechen und zu "wenigstens zwölf Jahren Freiheitsstrafe" zu verurteilen.
Das Obergericht stellte am 21. November 2008 fest, die Anschlussappellation der Generalprokuratur sei dahingefallen und das Urteil des Kreisgerichts V Burgdorf-Fraubrunnen vom 13. Dezember 2007 sei in Bezug auf die unangefochten gebliebenen Schuldsprüche in Rechtskraft erwachsen, sprach X._ zusätzlich der vorsätzlichen Tötung schuldig und verurteilte ihn zu 12 Jahren Freiheitsstrafe.
B. Mit Beschwerde in Strafsachen 6B_337/2009 beantragt die Generalprokuratur, dieses obergerichtliche Urteil aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
Mit Beschwerde in Strafsachen 6B_422/2009 stellt X._ den nämlichen Antrag.
C. Vernehmlassungen wurden keine eingeholt.

Erwägungen:
1. Beide Beschwerden richten sich gegen dasselbe Urteil und stehen in engem sachlichem Zusammenhang, weshalb die Verfahren zu vereinigen sind.
2. Beschwerde 6B_337/2009
2.1 Das Obergericht erwog im angefochtenen Entscheid (S. 8 f.), der stellvertretende Generalprokurator habe in seinem mündlichen Parteivortrag beantragt, die Rechtskraft der unangefochten gebliebenen erstinstanzlichen Schuldsprüche festzustellen und den Beschwerdegegner zusätzlich wegen vorsätzlicher Tötung zu "wenigstens 12 Jahren" Freiheitsstrafe zu verurteilen. Damit beantrage er keine Abänderung des erstinstanzlichen Urteils, weshalb auf die Anschlussappellation mangels rechtlich geschützten Interesses nicht einzutreten sei.
2.2 Mit seiner Beschwerde wirft der stellvertretende Generalprokurator dem Obergericht vor, das kantonale Verfahrensrecht willkürlich angewandt und eine formelle Rechtsverweigerung begangen zu haben. Bereits die prozessuale Vorgeschichte zeige, dass es ihm darum gegangen sei, das Schlechterstellungsverbot zu beseitigen und dem Obergericht zu ermöglichen, die Strafzumessung ohne diese Schranke neu zu beurteilen. Er habe sogar erwogen, eine Freiheitsstrafe von 13 Jahren zu beantragen.
2.3 Unbestritten und unbestreitbar ist, dass das Obergericht von Amtes wegen zu beurteilen hat, ob es auf ein Rechtsmittel einzutreten hat. Zu den dabei zu prüfenden Sachurteilsvoraussetzungen gehört unter anderem das Vorliegen eines aktuellen Rechtsschutzinteresses. Kein solches hat von vornherein, wer sich mit dem erstinstanzlichen Urteil abfindet. Ein rechtlich geschütztes Interesse an der Ergreifung einer Anschlussappellation hat mit anderen Worten nur, wer dessen Abänderung verlangt. Die Anschlussappellation bezog sich einzig auf die Strafzumessung. Der stellvertretende Generalprokurator beantragte, den Beschwerdegegner zu "wenigstens 12 Jahren Freiheitsstrafe" zu verurteilen. Dieser Antrag bedeutet klar und unzweideutig, dass dieses Strafmass nach der Auffassung des Antragsstellers zwar am unteren Rand des Vertretbaren liegt, aber eben noch vertretbar ist. Eine Abänderung der erstinstanzlich ausgesprochenen Strafe wird damit nicht verlangt. Dass nach Art. 337 des Berner Gesetzes über das Strafverfahren vom 15. März 1995 (StrV) mit der von der Staatsanwaltschaft eingereichten Appellation das Verschlechterungsverbot dahinfällt, ändert nichts daran, dass der stellvertretende Generalprokurator keine Abänderung des erstinstanzlichen Urteils beantragte und damit kein Rechtsschutzinteresse an der Ergreifung eines Rechtsmittels hatte. Das Obergericht ist klarerweise zu Recht nicht auf die Anschlussappellation des Beschwerdeführers eingetreten. Es hat dabei weder das einschlägige Prozessrecht noch die Verfassung verletzt. Die Beschwerde ist offensichtlich unbegründet.
2.4 Die Beschwerde 6B_337/2009 ist somit abzuweisen. Kosten sind keine zu erheben (<ref-law>).
3. Beschwerde 6B_422/2009
3.1 Nach der Überzeugung des Obergerichts hat sich am 7. Januar 2006 Folgendes abgespielt (angefochtener Entscheid S. 9 ff.):
W._ und Y._ sind in der gleichen serbisch-montenegrinischen Stadt aufgewachsen und verübten seit der Entlassung von Y._ aus der Haft vom 29. September 2005 in wechselnder Zusammensetzung, zum Teil mit Z._ und/oder X._, zahlreiche Einbruchdiebstähle. Für den Abend der orthodoxen Weihnachtsfeier vom 7. Januar 2006 luden W._, Y._ und X._ zwei Frauen in die Wohnung des abwesenden Z._ ein. Diese trafen um ca. 19 Uhr ein und verliessen die Wohnung nach dem Abendessen um ca. 21 Uhr wieder. In der Folge kam es unter den drei erheblich alkoholisierten Männern, die weiterhin Wodka tranken, zum Streit. W._ hänselte sowohl Y._ als auch insbesondere X._, dem er vorhielt, er habe wegen seiner Fettleibigkeit keinen Erfolg bei Frauen und tauge nicht für Einbruchdiebstähle. In der Folge wurde W._ von Y._ mehr scherzhaft bzw. "freundschaftlich", von X._ indessen ernsthaft geschlagen. Letzterer versetzte W._ mit einer Pistole eine Serie schwerer Schläge an den Kopf (insgesamt über 20) und fügte ihm Fusstritte mit grosser Wucht gegen den Oberkörper zu. Diese Verletzungen führten zum Tod von W._, der entweder an den ausgedehnten Quetschwunden am Kopf verblutete oder erstickte, sei es, weil ihm der zertrümmerte Brustkorb das Atmen verunmöglichte oder weil er als Folge einer Bewusstseinstrübung massiv Mageninhalt einatmete.
3.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, es sei denn, deren Beweiswürdigung erweise sich als offensichtlich unhaltbar bzw. willkürlich (Art. 97 Abs. 1, Art. 105 Abs. 1 und 2 BGG). Für Willkürrügen gelten strenge Begründungsanforderungen. Es genügt nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Es ist vielmehr in der Beschwerdeschrift (<ref-ruling> E. 3.1) nachzuweisen, dass die vorinstanzliche Beweiswürdigung offensichtlich unhaltbar ist (<ref-ruling> E. 2.2, 133 II 249 E. 1.4.3).
3.3 Der Beschwerdeführer legt in der Beschwerdeschrift über Seiten hinweg und teilweise gestützt auf unzulässige Verweise dar, wie sich der Tatverlauf seiner Auffassung nach abgespielt hat oder haben könnte, ohne auch nur ansatzweise zu begründen, dass und inwiefern die von seiner Sicht der Dinge abweichenden tatsächlichen Feststellungen des Obergerichts unhaltbar sind. Darauf ist nicht einzutreten.
Dies gilt auch, soweit der Beschwerdeführer die unrichtige Anwendung von <ref-law> bzw. Art. 18 Abs. 2 aStGB und die Verletzung von "in dubio pro reo" rügt (Beschwerde S. 8 f.). Unter diesem Titel legt er dar, dass er W._ weder habe töten wollen noch dessen Tod in Kauf genommen habe, er mithin weder mit direktem Vorsatz noch mit Eventualvorsatz gehandelt habe. Ersteres wird ihm nicht vorgeworfen, und die Bestreitung des zweiten begründet der Beschwerdeführer mit eigenen, von denjenigen des Obergerichts abweichenden tatsächlichen Feststellungen, wiederum ohne jegliche Begründung, inwiefern diese willkürlich sein sollten.
4. Der Beschwerdeführer macht geltend, das Obergericht habe ihn zu Unrecht wegen vorsätzlicher Tötung verurteilt.
4.1 Wer vorsätzlich einen Menschen tötet, erfüllt den Grundtatbestand der vorsätzlichen Tötung von <ref-law>, es sei denn, er sei besonders skrupellos vorgegangen und habe dadurch den qualifizierten Mordtatbestand (<ref-law>) verwirklicht. Handelte er dagegen in einer nach den Umständen entschuldbaren Gemütsbewegung oder unter grosser seelischer Belastung, kommt der privilegierte Tatbestand des Totschlags (<ref-law>) zur Anwendung.
4.1.1 Die heftige Gemütsbewegung stellt einen besonderen psychologischen Zustand dar, der nicht pathologisch begründet, sondern dadurch gekennzeichnet ist, dass der Täter von einer starken Gefühlserregung überwältigt wird, die in einem gewissen Grad seine Fähigkeit, die Situation einzuschätzen oder sich zu beherrschen, einschränkt. Typisch ist, dass der Täter mehr oder weniger unverzüglich auf ein Gefühl, das ihn plötzlich überwältigt, reagiert. Beispiele solcher Gefühle sind Jähzorn, Wut, Eifersucht, Verzweiflung, Angst oder Bestürzung. Mit der Privilegierung wird der Tatsache Rechnung getragen, dass der Täter aufgrund des emotionalen Erregungszustandes im Moment der Tötungshandlung nur noch beschränkt in der Lage war, sein Verhalten zu kontrollieren (<ref-ruling> E. 2a S. 203; <ref-ruling> E. 2a S. 236; STRATENWERTH/JENNY, Schweizerisches Strafrecht, BT I, 6. Aufl. 2003, §1 N 29; CHRISTIAN SCHWARZENEGGER, in: Basler Kommentar, Strafgesetzbuch II, Basel 2003, Art. 113 N 4).
4.1.2 Die heftige Gemütsbewegung muss überdies entschuldbar sein. Nach der bundesgerichtlichen Rechtsprechung setzt der Begriff der Entschuldbarkeit voraus, dass die heftige Gemütsbewegung (und nicht etwa die Tat) nach den sie auslösenden Umständen gerechtfertigt und die Tötung dadurch bei ethischer Beurteilung in einem wesentlich milderen Licht erscheint. Abnorme Elemente in der Persönlichkeit des Täters (wie besondere Erregbarkeit oder krankhafte Eifersucht) vermögen die Entschuldbarkeit der Gemütsbewegung nicht zu begründen, sondern sind allenfalls bei der Strafzumessung zu berücksichtigen. Eine heftige Gemütsbewegung ist entschuldbar, wenn sie in Anbetracht der gesamten äusseren Umstände als menschlich verständlich erscheint. Es muss angenommen werden können, auch eine andere, anständig gesinnte Person wäre in der betreffenden Situation leicht in einen solchen Affekt geraten. Hat der Täter die Konfliktsituation, welche die Gemütsbewegung auslöste, selber verschuldet oder doch vorwiegend durch eigenes Verhalten schuldhaft herbeigeführt, so ist der Affekt nicht entschuldbar (<ref-ruling> E. 3a und b S. 101 f.; <ref-ruling> E. 2b/bb S. 106; Urteil 6S.790/1995 vom 7. August 1996 E. 1a, in: Pra 1997 S. 60 Nr. 14).
4.2 Für das Obergericht (S. 66 f.) ist die Tat des Beschwerdeführers weder besonders skrupellos noch in irgendeiner Weise entschuldbar. Er sei zwar von seinen Kumpanen wegen seiner Korpulenz und seiner mangelnden Trinkfestigkeit gehänselt worden, doch seien diese Sticheleien im Rahmen des unter ihnen Üblichen geblieben. Er sei nicht plötzlich mit etwas Neuem konfrontiert worden, das ihn hätte überwältigen können. Er habe W._ schon lange verhauen wollen, und dessen langandauernde "Abschlachtung" sei nicht vereinbar mit einer Gefühlsaufwallung, die nur einen kurzen Moment dauern könne. Zudem sei seine Motivation letztlich egoistisch gewesen. Er habe W._ zeigen wollen, wer der "Coolere" sei. Der Beschwerdeführer habe sich wohl in einer gewissen Drucksituation befunden, da er sich alleine und ohne Papiere in der Schweiz aufgehalten habe und von seinen Kumpanen als wenig trinkfest, für Frauen unattraktiv und für Einbrüche ungeeignet gehänselt worden sei. Es sei indessen nicht erstellt, dass er von seinen Kumpanen systematisch ausgegrenzt worden sei, und er habe seine schwierige Situation durch seine illegale Einreise, seine Absicht, sich seinen Lebensunterhalt mit Diebstählen zu verdienen und seinem Alkohol- und Drogenkonsum zudem weitgehend selber verschuldet.
4.3 Wie das Obergericht plausibel darlegt, musste der Beschwerdeführer am Tatabend die üblichen Sticheleien und Hänseleien wegen seiner Korpulenz über sich ergehen lassen. Dass er dabei von W._ zudem mit einem vulgären Schimpfwort ("picka") eingedeckt wurde, kann angesichts des groben Umgangstones, den die drei Männer untereinander pflegten, die Eskalation des Streits bzw. die Überreaktion des Beschwerdeführers weder erklären noch entschuldigen. Dieser hat denn auch nicht in einer Gefühlsaufwallung kurz zugeschlagen um sich gegen die Hänseleien zu wehren, sondern hat seinem Opfer über Stunden hinweg mit einer Pistole in mehreren Serien harte Schläge an den Kopf verpasst und ihm anschliessend, als es bereits blutüberströmt und zu keinem Widerstand mehr fähig war, mit Fusstritten den Brustkorb zertrümmert. Dieses Vorgehen - der medizinische Experte spricht bildlich von "Zu-Tode-Prügeln" und "Zu-Tode-Treten" - zeigt, dass es dem Beschwerdeführer darum ging, W._ eine Lektion zu erteilen. Das Obergericht hat Bundesrecht nicht verletzt, indem es dem Beschwerdeführer keinen entschuldbaren Affekt zu Gute hielt und ihn wegen vorsätzlicher Tötung verurteilte.
5. Was der Beschwerdeführer gegen die Strafzumessung des Obergerichts (S. 67 ff.) vorbringt, ist nicht geeignet, diese bundesrechtswidrig erscheinen zu lassen.
Entgegen der Behauptung des Beschwerdeführers hat das Obergericht den Umstand, dass es von einer eventualvorsätzlichen, nicht von einer direktvorsätzlichen Tat ausgeht, zu seinen Gunsten berücksichtigt, wenn auch nur "ganz leicht" (S. 70). Seine Auffassung, die Tat liege im Grenzbereich zum Totschlag, wird vom Obergericht zu Recht nicht geteilt. Immerhin hält es ihm die Provokationen des Opfers leicht strafmindernd zu Gute (S. 70). Nicht zu beanstanden ist, dass das Obergericht "von einer durchschnittlichen Einsatzstrafe für den Tatbestand der vorsätzlichen Tötung - d.h. für einen Referenzsachverhalt ohne Vorliegen besonderer Strafminderungs- oder -erhöhungsgründe - von 12 Jahren" ausgeht, ebensowenig wie seine Beurteilung, dass sich diese vorliegend die Waage halten und die schuldangemessene Strafe damit 12 Jahre beträgt.
6. Die Beschwerde 6B_422/2009 ist somit abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig (<ref-law>).

Demnach erkennt das Bundesgericht:
1. 1.1 Die Beschwerde 6B_337/2009 wird abgewiesen.
1.2 Es werden kein Kosten erhoben.
2. 2.1 Die Beschwerde 6B_422/2009 wird abgewiesen, soweit darauf einzutreten ist.
2.2 Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, 1. Strafkammer, schriftlich mitgeteilt.
Lausanne, 16. Juli 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Störi