yes indeed, this is easily possible. in fact as Leffman says you don't even need to change all the colours on one line, you could change them one at a time, in fact i think that might even look better, if you staggered the colour changes you wouldn't see the point where it changed so easily. If they all changed together you might notice a "step".
although looking at that particular background image, you only need to change one colour per scanline anyway since you could just cycle the colours around on the image, like in a ring buffer. in other words, instead of a transition from a palette "001, 002, 003, 004" to "002, 003, 004, 005" one could simply change the first colour to get "005, 002, 003, 004" but remap the image to look the same.