For a more simpler history on this, check out Paula Cracker's page here.
Interviewer: What more could you ask for?
Murdoc: A decent guitarist.
Interviewer: And the only weakling appeared to be Paula, the guitar player.
Murdoc: I think we can skip this.
Interviewer: Who's Paula?
Murdoc: It doesn't matter, it's history.
Interviewer: No, come on. Who's Paula?
Murdoc: (Sigh) Paula was a girl who played guitar for us early on. And 2-D was seeing her.
2-D: My girlfriend.
Murdoc: Whatever. But she...er...didn't quite really work out with the band.
Interviewer: After Russel joined the band, Paula, 2-D's girlfriend of the time was drafted in to play guitar. But one night Russel found Murdoc and Paula up to no good in the toilets at Kong.
Murdoc: Cubicle number 3, I seem to remember.
Interviewer: For this gross act of disloyalty, Russel broke Murdoc's nose a further five times, giving us a grand total of eight fractures that afflict his mangled hooter today.
Paula Cracker, Gorillaz' first guitarist tells her side of the story:
Paula: Well, I'd been seeing Stu-Pot for about two months. I played a bit guitar and use to buy strings at the shop he worked in. He was very sweet. A bit thick though. He said that he was gonna be a singer in this band yeah? They didn't have a name yet. And I thought yeah heard all that before. Still I went to Kong Studios to check them out and played with them. But when I saw Murdoc with his thick, greasy hair, green teeth and yellow skin I thought "Ohhh! He's the one for me."
Interviewer: Paula becomes more increasingly animated. Maybe she's on some sort of medication.
Paula: Oh! He's such a dandy. Like Errol Flynn or something. But after that thing in the toilets they kicked me out,but I never heard from Murdoc again,and my purse was gone. Since then, they became this big massive band so I guess I was pleased for them. But it also makes me kinda sick in the head... like I want to hurt people. They try to write me off the story of Gorillaz. But I was the guitarist way before that Noodle. I've got half of mind to hunt them down, and start screwing with their heads.
Interviewer: I think she is on medication. 2-D seems hurt.
2-D: I can't believe you did that, Murdoc.
Murdoc: I did you a favour, man. She was a rubbish-looking bird. Seriously, she looked like Grayson Parry or something. You're best shot of her.
2-D (quitely): ...It's just the principal.
Murdoc: Look, she was depressingly ugly. Easily enough to put you off your dinner. You should thank me. Anyhow, on with the show...