I think you've picked a hard one!
So, this is a fixed expression:
(see http://www.englishpage.com/gerunds/expression_ing.htm)
And... here are my thoughts:
difficulty is a noun, but in the above context when you use it with the verb "to have", it presents a special case fixed expression.
to have difficulty..., having difficulty...
In which case, the following verb + ing is always a gerund.
(You've also given a further example of the phrasal verb "to fall asleep" (other examples: "to keep up", "to turn up") which follows the same gerund making rule , ie, :"falling asleep". A little tricky but still follows the rule)
I feel that the fixed expression sort of transforms the roles of the noun and verb, because the part "to have difficulty" is kind of the adjective and the it describes the verb+ing, which is turned into a gerund (noun).
This is not authoritative, I wouldn't mind if someone came and cleared this up too, but I hope it makes sense.