Using another company's logo in my company's video - I don't seem to have a choice

So I am working on a start up company in the fitness sector. Besides a couple of other things we are making training videos for fitness instructors, to show them how to do the moves and such. Our models in the video (the inventors of the program) have to wear proper shoes to perform the moves. And proper fitness shoes are always branded with a big old logo on them.

The owner of this trademark says on their website that they wont grant permission:

(We do) not grant permission to use or modify our trademarks, logos,
images, advertising or similar materials.
It is your responsibility to determine whether your proposed use is
legally permissible. For example, some uses of our logos in a textbook
may be considered “fair use.”

(Our company) regrets that due to the time required and cost involved,
we cannot fulfill these types of requests.

I dont see myself having a choice but to show their logo in our video. We are not a competitor, but we also don't wanna make it look like the company has endorsed us to showcase their product (product placement). I feel like there is a risk to include their logo because there is a chance of them not liking our stuff (We are doing fitness for the general population, but you never know...)

Putting some duct tape over the logo is going to look quite ugly... Especially on video.

Any suggestions?

Am I allowed to use their logo, as long as I mention at the end, that they didn't sponsor us?

Do I have to find a different solution (like cover up the logo somehow)?

I went ahead and did the following:

Got some fabric in the same color as the shoe, and cut out a shape that looks ok and masks the logo completely. It wont be invisible, but should not be extremely noticeable on video... Would have been really nice if I could have gotten OUR logo on there instead, but I don't have enough time left, and I don't want to re-brand shoes, which the shoe company may have some copyrights on the design or what not...

BrianAdkins' link to the discussion in another forum had some good points in it, especially this one:

If you have a workout video, and you displaying nike logo. and for
some reason they (nike) doesn't like what your representing... they
can and they do take action. for example it could be some thing as
simple, as the actor sweating, or maybe being a little over/under
weight, or maybe the music sample. all they have to do is tell the
courts, you have hurt they image they have been building .... and
guess who is going to win that battle.

Down the road maybe Nike or some other company will like what we do and chooses to endorse us, then we'll be sure to display their logo - unless our own clothing line is in the works by then, which would make us a competitor to Nike or whomever... ;-)

I'm not a lawyer, but I see a precedent here. The instructor is wearing new balance shoes, you have to look hard to see it, but the logo's there. Given this particular instructor is highly unlikely to have an 'endorsement' from NB, I have to say this qualifies as fair use. I'd say showcasing would be something like wearing the same brand shoes, shirts, hats, pants, waterbottles, etc.

Also, for added security you could put a disclaimer in the video along the lines of

'The endorsement of Company X by Shoe Company is neither intended nor implied'.