Either there is something wrong with you match history or "everytime you tried" is once and that one doesn't look too bad.
A common mistake of Nasus in the jungle is putting ranks in Q. This is suboptimal, it gives little damage and you are not killing mobs as fast as minions, so the cdr doesn't matter either.
edit: clarified some details.
Also don't try to last hit all mobs, that only wastes time and life, start with one small mob, then you have the cooldown back for the big mob, just kill off the other small one and head to the next camp.
What you need to do is level E for fast clears (gold to get ahead!), and W for good ganks (more gold!). My best order seems to be QEWE or QEEW then WRWQW. Then max Q and finish E last.
After the laning phase is over you can start worrying about your stacks, that's why you max Q second, because you have more access to minions.
I'm not entirely sure about Devourer, on one hand he is killing a lot of mobs, so it's gonna stack a lot, but on the other hand he is alread stacking anyway. Juggernaut or Magus would give hjim something he lacks.
Also don't get two spellblades. Except for the AoE on Iceborn, they don't stack.