In the video tutorial I’m following the instructor is using 2.72. In that version there was a dropdown menu available in the Slots tab, called Add Texture Paint Slot. Have a look at the images below:
Now in 2.75 this is what’s there now:
Switching to Image from Material doesn’t lead to what was there before. Nor it makes any difference whether you’re using BI or Cycles.