That woman was just a Reaper, not the new Death.
I wouldn't be so quick to dismiss Billie as the new Death--we've seen angels step up and take on the role of leader of heaven (and, in Metatron's case, the role of "the new God"), so I actually have a fairly easy time imagining a Reaper stepping in to fill the role of Death.
Yes, it wasn't actually stated in the ep, but she did talk like she was in charge, or planning to be.
I really really really don't want old Death to be gone, but recently the show has a history of dumping beloved characters in a pretty paltry way, e.g. Charlie, Garth (and I personally was really pissed when Balthazar left the show). I'd love to see Death return, but I'm not going to hold my breath.

I doubt he's really dead, just somewhere putting himself back together and planning to revenge himself very terribly on the brothers. Maybe even unlocking Lucy's cage just as a final FU to them, not bothering to manifest on Earth again after that.
Yes, it could make sense if Death, when killed, ended up in the Cage. Don't know if it's so, though....