Most patience games, as you've noted, require logical deduction, but most still require a degree of luck.
Spider Solitaire and Mrs. Mopp come close to being solely skill-based, but are both still vulnerable. FreeCell is another game for which almost all games are thought to be playable, though the proportion has not yet been calculated. A rough estimate of winnable games was calculated to be around 99.9987% of games.
However, there are a number of games which do not rely on luck if one assumes the game is winnable (as opposed to games like Aces Up, which are almost solely winnable based on luck). Scorpion is an example of a solitaire game which takes significant skill to actually win, even if the game is winnable. Calculation additionally is almost always winnable, but takes significant amounts of strategy to actually claim a victory (in most cases).
Klondike actually does not fall into this category, as you are blind to the cards much of the time, and frequently would actually be better off taking your chances as opposed to playing logically.
I could go on, and may feel like editing more examples in later, but the short answer is: there are card games for which mostly skill is required, and card games for which, if victory is possible, significant skill is often required to achieve it. Whether there are card games which are provably always solvable remains to be seen.