Including code from non-free libraries will make your package non-free.
Not true. The result would be illegal, not non-free.
The license of the library might permit one to use code from it, but still might make it non-free in the sense of the GNU GPL. For example, it might restrict the terms of redistribution.
No, it would make it illegal. You wouldn't have any right to do anything with it, not even smell it. You just can't mix GPL code with non-free code in anyway unless the copyright holder gives you permission for it in a legally binding way.
For it to be legal the whole work has to be licensed under the GNU GPL.
I think this might not be quite correct, depending on what is meant by "the whole work". There are licenses considered by the FSF to be compatible with the GNU GPL.
The question was about a non-free program/library + a GPLed program/library; so in this case the whole work must be under the GPL. This was what the OP asked about, not about mixing the GPLed code with a GPL compatible license.
To be absolutely sure about licensing matters, it's always best to ask the people at the FSF who specialize in them.
Indeed!