I vote for Shinx!
The main protagonist could find it thinking, "oh god, this thing looks so weak" but catching it anyway since he couldn't find anything better. Then he'd end up reluctantly training it and having it evolve into total-badass electric lion. Just my thoughts. :P
Oh, the same could be applied to Ralts (at least if it was male and evolved into Gallade).
I LOVE Chocolate-kipp's mentality for the starter....I think applying that to any starter would be fantastic. .
My vote goes to Growlithe.
Cubone is a close second, but combined with chocolate-kipp's mood setting and my previously mentioned 'man's best friend' attitude of a Growlithe who just wants to make his disappointed owner happy, I think the stage could be set for some powerful storytelling. Therefore, I vote Growlithe.
The main issue I see with this story premise is that with the fainting=death rule in affect it would be difficult to pull off... I couldn't have the starter getting his ass beat a lot @ the beginning to make this premise work well.