First, the usual rules: LA is included in ECL when calculating XP. The catfolk druid, therefore, had at least 6,000 XP to have ECL 4th (druid 3rd +1 LA), and loses a level from reincarnate. When you lose a level, you go down to halfway between the previous level and the level lost, so 4,500 XP. His race also changed and he loses the LA +1, so 4,500 XP is enough to keep his 3rd level of druid.
From there, the XP rules would have the druid about half a level behind, and he would gradually catch up as the group levels since he would get more XP than those who are higher level. So initially he is 3rd-level, and they are 4th. Eventually, he levels up to 4th, so the whole party is at 4th for a while, but then they level up to 5th before he does, so he is a level behind for a while again. This repeats for each level for several levels, but each time the amount of time the druid spends a level behind shrinks. Eventually, it disappears altogether and the party is all at the same level.
Now, story-based leveling: the DM would have to find decent “halfway points” between the rest of the party’s leveling and the druid leveling. Moreover, these “halfway points” would have to slide, so that at higher levels the druid’s delayed level-up occurs sooner and sooner after the rest of the party—less “half” way, and more like a third of the way, a quarter of the way, etc. Eventually, the delay should disappear entirely, and the party should all be on the same level now.
But personally, this is not what I do, and I always use story-based leveling. What I do is eliminate split-level situations altogether. LA is rarely used in my games; I usually try to develop an LA-less solution to letting the player play as a given thing. And resurrection abilities don't reduce anyone's level. As a result, I don't have to worry about any of this.
And I do that because I think all of these mechanics are atrocious. They result in a lot of headaches and extra work for the DM, and a lot of frustration and annoyance for the players. It makes it much more difficult for everyone to participate. Moreover, particularly in a story-based game, punishment for death is unnecessary: dying (and temporarily being unable to play) is the “punishment.” As @anaximander said in a comment,
In some games, the punishment for dying is that you died. In games that use story-based levelling, there's often a heavier emphasis on story (obviously), so players can get quite attached to their characters. When that character dies, it's sufficient punishment that the player loses the character they love, cutting off any story they had planned for them, and that the rest of the party has to deal with that. Adding extra penalties in the form of XP loss etc. is just kicking them when they're down.
This remains true even if the PC gets resurrected, because resurrection itself is not free. How difficult it is to get, how much the PCs have to shell out to get it, these things are appropriate ways to control how much death “matters” in character (and I have played in and run games that run the gamut from “resurrection is just flat-out unavailable,” to “you resurrect instantly and for free at the end of the fight,” the last in a Diablo II-themed game).
So I recommend actually letting the druid level up from this, since the LA +1 is being removed, and making him 4th level like the rest of the party. Then you never have to worry about these problems again.