This exact question is asked by Malbim.
איך הרגו על פי הודאת עצמו ואין עדים והתראה
He provides three possible answers:
The fellow was not Jewish and just as other judicial conditions do not apply to non-Jews, it is possible that inadmissibility of self-incriminating testimony does not apply to non-Jews.
The fellow was Jewish but David was allowed to kill him in his capacity as king even without formal court proceedings.
The Sages say that the fellow was Doeg, and even though he could not be held culpable for this self-admitted killing, he was culpable for the destruction of Nov the city of priests, and thus David executed him for that.
דמך על ראשך אם נאמר שהיה עמלקי ממש שבן נח נהרג בלא התראה ונהרג אף על הטריפה ונהרג בדיין אחד ובעד אחד י"ל שהוא הדין שנהרג בהודאת עצמו כמו שנהרג על פי קרוב (וצ"ע בזה לדינא) ועל זה אמר פיך ענה בך ואם נאמר שהיה ישראל נהרג מדין המלכות כמ"ש כי פיך ענה בך לאמר אנכי מותתי את משיח ה' כדי שלא יזידו להרים יד במלך ולקבלת חכמינו זכרונם לברכה שהיה דואג שהיה חייב מיתה מכבר על נוב עיר הכהנים שעל זה אמר דמיך בלשון רבים רמז לו שהגם שעל הריגת שאול אין אדם נאמן על עצמו בכל זה פיך ענה בך כי כבר היית הגורם על הריגת הכהנים והכהן המשיח שזה רמז באמרו אנכי מותתי את משיח ה׳
Ralbag, while not explicitly asking this question, addresses it by saying that David executed the fellow as a hora'at sha'ah, a temporary extra-judicial ruling, so that people wouldn't think that it is trivial to kill the king.
ואעפ"י שלא היו שם עדים והיה מרשיע את עצמו והיה מפני זה פטור בדין הנה עשה דוד זה להוראת שעה שלא יקלו האנשים לשלוח ידם במלכות ולזאת הסבה בעינה נזהר משלוח יד בשאול כשהיה במערה ואעפ"י שהיה רודפו והיה מותר להרגו