koko de kutu wo nuide mo ii desu ka?

脱いで is the て-form of 脱ぐ (to take off). When you want to attach もいいですか to ask permission, you need the verb in its て-form. The structure is:
Verb(て-form) + もいいですか?
So 脱いで + もいいですか gives you “May I take off…?”

This is the standard polite way to ask for permission:
Verb(て-form) + もいいですか？
Literally “Even if I do X, is it good?” → “May I do X?”
In our sentence, 脱いで (take off) + もいいですか = “May I take off (my shoes)?”

The も is part of the fixed expression てもいい. Without it, ていい is either ungrammatical in formal speech or a very casual/slangy version. Always remember:
～て + も + いい = permission.
Dropping も is possible only in very casual contexts.

ですか makes the question polite and formal. If you’re speaking casually to friends or family, you can drop ですか and simply say:
ここで靴を脱いでもいい?
or even add a friendly particle:
ここで靴を脱いでもいいよ？

脱ぐ (to take off [clothes, shoes]) is a transitive verb, which takes a direct object. The object here is 靴 (shoes), so you mark it with を:
靴を脱ぐ = “to take off shoes.”

Yes. Japanese allows flexible word order as long as particles stay attached. For example, you could say:
靴をここで脱いでもいいですか？
It still means “May I take off my shoes here?” The emphasis just shifts slightly.

To grant permission:
はい、いいですよ。 (Yes, it’s fine.)
どうぞ。 (Go ahead.)
To refuse or ask someone not to:
すみません、ここでは脱がないでください。 (Sorry, please don’t take them off here.)
だめです。 (That’s not allowed.)

• ～てもいいですか？ is a polite question asking permission (“May I…?”).
• ～てもいい (without ですか) can be:
  • A casual question (“May I…?” among close friends).
  • A statement of permission (“You can…”) when you add something like よ: 入ってもいいよ。 (“You may enter.”)