Interestingly enough, when considering not just the set of "typical" or "known" substances, but the vastly larger amount of all possible compounds, almost all pure substances do not have a thermodynamically stable liquid state or gaseous state. To become a liquid, a molecule must gain enough energy to set itself loose from the tug of its neighbours in the solid state. Typically intermolecular forces are fairly weak, and so for simple molecules this energy can be provided at relatively low temperatures.
However, there is no upper bound on how strong the intermolecular forces between two molecules can become; just take an enormous molecule. Even with relatively weak intermolecular interactions between each atom, when summed up across a huge molecule, the required energy becomes vast.
Combine this with the fact that, thanks to combinatorics, almost all possible substances are composed of massive molecules (in a chemical analogue of the frivolous theorem of arithmetic). For example, there are only five possible distinct substances with the formula $\ce{C6H14}$, but over a trillion trillion trillion trillion ($10^{48}$) distinct molecules with formula $\ce{C120H242}$.
The conclusion is that almost certainly the molecules would decompose (breakage of covalent bonds) well before getting close to the extremely high temperatures needed to produce a true liquid state.
Therefore, there should be many, many examples to choose from. A heavy-handed example would be maitotoxin (or many other natural products). Though the theoretical melting point would be very high, the presence of all those hydroxyl groups suggests it would decompose by dehydration around ~200 °C, as is typical of polyols (I'm sure it would actually decompose much sooner).
In the same polyol vein, a much more relatable example would be sucrose (sugar). In the strict thermodynamic sense, sugar doesn't actually melt when heated on a stove. The clear colourless syrup that's formed is actually the first step in caramelization, the complicated thermal decomposition of sugar.
The above cases represent your first suggestion of possibilities. Polymers also fit, with the complication that artificial polymers are almost never actually pure substances but mixtures of very similar molecular chains, varying in size. Something like your last suggestion is interesting, but examples seem hard to provide. Perhaps dinitrogen pentoxide is close, due to its unusual transition between ionic and molecular forms.
