I think John is a hero because he's still a human being at the core. The concept of anti-hero justifies acting the bastard to meet heroic ends, but the term just feels wrong for John. He's not going out to be heroic, he just has that nagging bit of humanity in him that wants to help. He lies, cheats, and makes mistakes. It's why we can relate to him on levels, because he's closer to us when he acts like a real person would. When he goes beyond and sacrifices to stop the evil he confronts, sometimes beyond what we would consider moral, that's when he becomes a hero. In the end he doing what's right makes a hero. John is everything that got man tossed from Paradise. The difference is he walked out on his own, lighting a smoke, and tossing the V on the way out.