Gaara's past makes Naruto's look like a cakewalk. Both have no parents (Gaara even seems to have memories of killing his...), both had to deal with being called monsters, both were isolated because of it.
But having your father try to kill you and the one person who seemed like they loved you actually hate your guts, man that shit is bad.
Sasuke's past had alot of bright spots, but you wonder if that makes the Itachi incident even more painful. Still, he had some good times before that and was popular amongst his peers (even though he didn't seem to enjoy it).
Neji had a pretty shitty past too, but again he was still top of his class, still managed to get acknowledged by the main branch of the Hyuuga family and also learned that his father's selfless actions were appreciated. Recently things have been better for him.
Zabuza I'm not sure about. He didn't seem sad (almost happy) about killing all his comrades. He seems to be quite content in the lifestyle of killing that he was raised in, although I wouldn't be surprised if he 'snapped' at some point. He did have to live with the failed coup, living as a fugitive, but he did also have...
Haku. Haku also had the 'i'm a monster' past going, and the entire thing with his parents was fucked up royally, but at least his mother seemed to really care about him. He was also abandoned for some unknown period of time, became a killer and a fugitive. But I got the feeling that he genuinely was happy because he had Zabuza.
Are we all forgetting about Kimimaro? That guy has a horrific past. No known parents, caged and neglected by his clan, forced to fight (which he did NOT seem to enjoy, he just did it). I'd imagine he had alot of I'm a monster angst going on that wasn't highlighted. Then he gets recruited by Orochimaru of all people, comes down with a fatal disease and 'dies' before he can serve his master. Then he's brought back to life and AGAIN dies before completing his mission while being ridiculed by Naruto, Gaara and Lee about the one bright spot: his serving Orochimaru. And that's a pretty shitty bright spot, but at least Kimi seemed to think of it as a good thing.
So, in sum,
1. Gaara
2. Kimimaro
3. Haku
We don't know enough about Kakashi from the anime yet to rank him here... but it looks like he'll be pretty high.