Learn Finnish: Mies nukkuu kirkossa. - The man sleeps in the church.

This specific sentence doesn't use it, but we can easily adapt it! If you wanted to say "The man comes from sleeping in the church", you would use the third infinitive elative of nukkua: Mies tulee kirkosta nukkumasta.

I remember that the verb nukkua has consonant gradation (kk -> k). Why does nukkuu still have a double k?

You're right about the consonant gradation! The double kk drops to a single k in the "weak" forms, like the "I" form (minä nukun). However, the third-person singular ("he/she/it") form always uses the "strong" grade. That's why the double kk remains in nukkuu.

Why does kirkossa use the -ssa ending instead of -ssä when it has a front vowel (i)?

This is due to vowel harmony. The word kirkko has the vowels i and o. While i and e are front vowels, they are considered "neutral" and will let back vowels (a, o, u) dictate the ending. Because of the o, the word takes the back vowel ending -ssa.