Letters really must be from professors. One possibility in some situations (e.g., you took a large lecture from a professor that was accompanied by a lab led by a PhD student) is to ask for a joint letter, or to have both of them write for you. The letter from the PhD student, though, would be "extra" unless it is also signed by the professor. The thinking is something like: "We want a letter from someone to attest that this student will succeed in our program, so the letter writer should be someone who truly knows what goes into that kind of success – i.e., should have a PhD and (ideally) have taught PhD students."
"3. I know one highly relevant academic very well but he hasn't taught me - he's more of a mentor. Would he work?"
Potentially. If you've discussed research with him (i.e., the relationship is not just social), then this might be a good bet.
"4. I also have a professional working relationship with the Dean, who is a very well respected academic. He wouldn't be able to write about my academic ability but certainly write about my working ability etc. Would he work?"
This is more doubtful. They really want someone to attest to your research ability, not your personality (though I'm sure that's great too )
"I've got my academic advisor who's a pretty well-established academic and who would write a very good LoR."
Definitely ask this person.
"Then there's the person I'm hoping will supervise my undergraduate dissertation next academic year. But the problem here is that he will only have known me for 3 months by the time I'm applying, which is next to nothing. He is the key figure to get a LoR from as he's been at my top two schools either as a PhD student or a Professor, so he'll most likely know a large percentage of the faculty, including admissions tutors."
Assuming you've established some relationship with this person before letters are due, ask this person as well. It actually seems sort of odd to not receive a letter from the undergraduate thesis advisor.