What structural property creates stickiness?
Long story short, no, sticky substances don't have to be nonpolar at all. Pour a little wine or beer on a table, and let it dry almost completely: it will get sticky, but still be water-soluble and hence polar. Also, there are certain water-based glues, which are surely sticky and polar. On top of all that, go read about the hagfish, only make sure you're not eating at the moment, for fear of adverse reaction.

As for the structural properties that make a substance sticky (or viscous, which is basically the same thing), these are not so easy to point out. Many sticky things are polymers, i.e., very long molecules with lots of van der Waals interactions, just like you said, and probably lots of interactions of other sorts, too. But this is hardly a rule, as exceptions both ways are plenty. Polyethylene is a polymer, but is not sticky at all. On the other hand, sugar syrup can be pretty sticky, despite containing no polymers.

As for the sticky solids, I would claim that there are none. Of the possible examples, some are actually highly viscous liquids, some are sticky because they are covered with such liquids, and some would stick to things because of electrostatic effects.