If you want to do this all on a single Arduino you indeed already need 3366 bytes to store the led info. So a Mega would suit that. You could also use a ESP8266. But it will even be possible on an Arduino Uno (/Pro Mini / Nano) with some memory tricks. Because (at least in the video) once the animation is finished all stairs display the same. So with 2 (stairs) x 66 (leds) x 3 = 396 bytes it possible. But indeed, the full 3366 bytes will ive you more option for animation.
But the hard part isn't the Arduino but the power management. Every stairs can draw up to 4A with a total of 68A! That is A LOT! That would require around 17mm2 
Or, what I would do, use 2,5mm2 per two stairs and group all of them at the power supply with multiple lower fuses (like 10A car fuses) in line.
And for the data lines, Don't forget to add a resistor in line with the data line between each stairs. The WS2812B is prone to break when the voltage on the data line is higher then the supply (which can happen because of the multiple voltage lines).