Is it still possible to write an appeal to the Editor-in-chief against the decision?
Sure, it's always possible to do that. Whether the appeal will get you anywhere is a different question. In this case, I feel like you think what you told us is grounds for an appeal which has a reasonable chance of being successful....but I didn't see anything in your post that would make me, if I were an editor of your journal [disclosure: I am not a journal editor; but I have dealt with journal editors regularly for some years now], reconsider the decision.
Basically they are saying that after addressing the comments they agree that your paper is solid and publishable, but is not worthy of publication in their journal. More specific words like "originality", "difficulty", "novelty", "value", "depth" all amount to this same judgment. Does a journal have the right to reject papers that they think are perfectly sound and publishable but not good enough for them? Of course they do!! The journal's right (and even obligation) to do just that is what allows the entire system -- in which some journals are more prestigious than others, and for which publication in the most prestigious journals (e.g. Nature and Annals of Mathematics) is a career-making accomplishment -- to function.
Unfortunately it is quite hard to successfully appeal this kind of verdict. In the rare case that you happen to know that the editors lacked some specific, objective, important piece of information that would have impacted their decision -- the referee's report dramatically mischaracterizes your work, say by neglecting to mention that you solved an important and well-known problem -- you can bring that to their attention. More often you suspect that they didn't properly appreciate your work, but your recourse is to resubmit to a journal of equal or greater prestige, and look forward to the (usually implicit!) "I-told-you-so" when your paper gets published there.
Maybe you thought that being asked to make revisions meant that the paper would be accepted conditionally on making those revisions in a way that satisfied the referees? Well, if you were specifically told that, then: Yes, appeal. You have a strong case. Otherwise: unfortunately, no, that need not be the case. If a referee feels that even if you made the revisions she would still not recommend the paper for acceptance, then the ethical thing to do is to reject the paper and make clear that the suggested revisions are for a version of the paper to be submitted elsewhere. However, even if the referees recommend the paper, then the decision to accept rests with the editors. As a general rule, the better the journal the more likely it is that a paper which was satisfactory to all the referees will still not be published. Some of these journals presumably don't even have the space to publish all the papers that their referees recommend them to publish, so they have to make hard choices.
There is one small word in your post which shouts to me: still. This suggests that one of the referees mentioned in her original report that your paper did not have enough originality to be published in the journal you sent it to. Is that right? If so: well, then is it really true that you addressed all the comments of the referees? In my experience, lines like this are often hints that the referee is not going to want to publish your paper even if you make some revisions which in your mind measurably improve the paper. Since "originality" is quite subjective, it is very hard to be confident that you are adding originality, and when you get a report like that it is often a good idea to check in with the editor to see whether s/he views that comment as a deal-breaker. (I can think of one instance where I got a comment like that, was asked to revise, and wrote back to ask the editor whether he really wanted me to revise the paper under the circumstances. He said yes and the paper was published. However the journal, while solid, was very far from the top one in my field.)