The very short answer - you do NOT need protein powder to lose weight.
(Actually, you don't need exercise to lose weight either!)
To lose weight, you need to create a calorie deficit. Expend more calories than you take in (or the equivalent - take in fewer calories than you expend). There are other more complicated factors that determine your body composition, especially how your metabolism is dictating how much you are in fact "expending", but raw body weight comes down to "Calories in vs calories out".
That said, however, for long term weight management exercise and a high protein diet will both contribute to improved body composition. There are massive numbers of studies which prove both of those points, for a host of reasons.
Based on what you say, I have doubts about the quality of your trainer, but he isn't entirely wrong to suggest protein powder. Physiologically, it's probably a premature recommendation. It is, however, a good habit forming suggestion.
Further, the best way to get lean and stay lean is to build more muscle. Having more muscle causes you to burn more calories everyday. As a ballpark, an extra pound of muscle will burn extra 15 calories per day. That doesn't sound like much, but let's say you gain 10 pounds of muscle. That results in burning an additional 150 calories everyday right off the bat. In a month, that's 4,500 more calories you'll burn. These numbers make a difference in the long run.
As a very basic argument in favor of your trainer's recommendation, protein powder will help you build muscle, which in turn will lead to less fat.