Help me out here!

There is an amazing anime that I watched a long time ago and I felt it was one of the best out there! I don't remember what it is called though, it has to do with a corporation that owns just about the entire world and they are fighting against the Resistance who want to take it back. It has a character that rides around in a Carriage and he helps fight of these Demon likes creatures that the comnpany has sent and in the end one of the main characters get killed and ends on an almost cliff hanger, The most memorable part is during the middle when an old man sings a song about the blues, this song is titled after the title and is the only part that is in english. If you know it please help me out, I am so frustrated about it and want to go out and get it again.