The current answer is incomplete. Installing libv4l-dev creates a /usr/include/linux/videodev2.h but doesn’t solve the stated problem of not being able to find linux/videodev.h. The library does ship header files for compatibility, but fails to put them where applications will look for them.
sudo apt-get install libv4l-dev
cd /usr/include/linux
sudo ln -s ../libv4l1-videodev.h videodev.h
This provides a linux/videodev.h, and of the right version (1).