wxWidgets seems to match your criteria, except for "skinable".
It depends on your definition of what is "easy skinable", but some approaches comes to mind:
1) Using bitmaps and handling everything yourself, pretty much like Winamp =<2.x.
2) Using the wxUniversal port, which you should only need to write a skin for it. This would be a good way, the only but, is that I don't know if there's any documentation for doing a skin. But you could actually look at the implementation of the current 2 skins it haves.
I'm not here to judge the skinable thing, I don't know what will be your user-base.
I personally prefer a very powerful program, not skinable and native looking but very customizable like the player foobar2000 instead of the 'skinable' Winamp, which doesn't let you customize how everything is displayed. I'm talking about the GUI interface.
Again, another advantage about using native widgets instead of a custom skin is that now that all modern OS supports skinability at the OS level, so every program using native widgets is pretty consistent with the rest.
One would only need to look at the consistence in interface between programs in Ubuntu or Mac OS X vs. Windows, and you can see what I mean.
In Windows it seems to be pretty common between developers to not use the Human Interface Guidelines of the platform, so it's like lot's of programs uses overdrawn widgets and skins. If you like or dislike that, it's up to the user, I personally like consistency.
But keep in mind, because you want cross-platform GUIs, in other platforms, specially MacOS, not respecting the HIGs of Apple will represent a direct relation of a decreased user base on that platform (becase any program not consistent there, is seen as wacky).
The native widgets vs. non-native widgets thing should be something to be considered more by the users, instead of the developers in a given platform.
I know another GUI toolkit that matches your criteria (it's skinable, but doesn't support native widgets), but I can bet for sure that if you use it, no one user would use it in Windows or MacOS.
I'm talking about GTKmm. I never seen a program written in it for Windows/MacOS used actually by anyone, and I can bet that it's because the native skins thing.
However I saw very popular programs with success in Windows/MacOS, written in wxWidgets or QT.
Examples can be (in the case of wxWidgets): VideoLAN, AOL Communicator, Kirix Strata, W3C Amaya, aMule, TortoiseCVS...
And the good thing is that probably most people can't tell the difference between a MFC/Win32 program and a wxWidgets program.
But all of that depends on your target.
