Let me try to explain what the sentences mean, before answering when I would use it. There are some incorrect words in the sentences, but I wouldn't correct them here because it just muddies the answers (I prefer to help understand you the flow of the sentences rather than try to correct every single word written).
1) "He couldn't not have paid the bill", the meaning is "it is not possible he did not pay the bill". Or another way to understand it:" He must have paid the bill. No way he didn't do it."
2) "It couldn't be he didn't pay the bill.", the meaning is the same as the first sentence. No obvious differences, the meaning is the same.
3) "It couldn't be he haven't paid the bill." the meaning is also the same as the first sentence. Again, no obvious differences- the double negatives somehow will negate themselves, depending on their use.
Now you know what they mean, let me just say that normally, I will try not to use them. Double negatives is a common occurance in some languages (say in Japanese or Greek), but in English I recommend keeping them to the minimum to improve readability.
The only time I would try to use them is when I write, where there is a lot of time to pick through the meaning. I don't try to speak it- it makes things too difficult for me as well as for the listener.