The tricky bit is that the air within a few millimeters of the treadmill will move with the treadmill. The air slightly above that will be slightly disturbed and also move a bit in the direction of the treadmill. If you had an extremely long and extremely wide treadmill (say the length and width of a runway) it's possible that the air at the height of the propeller would be moving along with the treadmill, rather than staying still, or moving with prevailing winds.

But, even in that case, the plane could still take off. All the plane needs to do is move the body of the plane through the air at enough speed to allow the wings to start generating lift. If the air at propeller-height is moving with a treadmill that is moving at take-off speed, the plane might take off with zero forward speed relative to the non-treadmill ground. But, as long as you're not somehow preventing the propeller from moving the plane through the air, the plane will always be able to take off.

There are videos of planes taking off by themselves in high wind, and videos of VSTOL (very short take-off and landing) planes taking off and landing using only a few metres of runway.