"Excuse me please, where do I find milk?"
Translation:Извините, пожалуйста, где мне найти молоко?
Yes, the construction would be somewhat similar to an English "Where is it [possible] for me to find milk"
With the "possible" implied. The English subject is "it", but it is a pretty abstract and "ethereal" subject (not a thing, not a person, not anything specific), so it is natural to omit it. [By the way, that last "it is natural to omit it" has just that same structure.]
Can anyone tell me what part of speech найти is? Does it change according to subject or does it stay the same? Thanks.
It is a verb in infinitive: "to find". You might be surprised because it does not end in "ть" like the majority of verbs. You can see in "http://russianlearn.com/grammar/category/table_of_russian_irregular_verbs" that there are a few verbs ending in "ти" and "чь" (like мочь)