Could physical (i.e. lego) models help teach CS?
It would, of course, be foolish to answer no, since you give an example of it. There is a Pedagogical Pattern, in fact, called Physical Analogy that suggest doing just this. Physical analogies of any kind help a student visualize the concept at hand. But it is this idea of aiding visualization that is key here, not the physical object itself. 

Metaphors and analogies of any kind are essential to teaching novices, linking their prior knowledge and experience to the new topics. But the pointer thing can also be taught at a white board with a bit of showmanship. "new" means draw a _cell, "next = " means draw an arrow. 

You can also provide a computer visualization that abstracts a bit from what the "professor" is showing in the video, which does, in fact use a bit of computer visualization along the way. 

But, while I'm a big fan of metaphor and analogy, I want to also provide a caution. The thing you are teaching is "similar to" but not "just like" the metaphor you use. Don't try to push the similarities too hard. At some point any metaphor breaks down and if the student has put too much currency into the similarity he or she may have trouble. Nodes and pointer are not, in fact, physical quantities, but only bit patterns. 

For a simple case like cells with next fields you can also do this. A person is a "cell". Their left hand holds a bit of "data" perhaps written on a piece of paper that they hold or some other physical object that they can use. Their right hand is a "pointer" to another "cell" (i.e. person). You can build up a linked list in this way. You can modify the data in a cell, you can modify where "next" points to, etc. If the class is large this may be more effective than the lego idea since it can be viewed by a larger audience. It is also more active than just viewing a "professor" manipulate blocks on a table. 

Also, metaphor isn't limited to such low level ideas and can be used at any level. "A database is like...". They are only limited by the creativity of the teacher and the willingness to work at it to get it right. The make a peanut-butter sandwich as a way to introduce algorithms is often used, but the knowing teacher also knows that no one is really likely to treat making lunch as a true algorithm. There it is the differences that are essential to the learning, since over interpreting an "algorithmic" description leads to trouble (and messy floors).