As I understand it, you are asking two questions: (1) are there e.g. SAT algorithms that are more clever than naive brute force, and (2) are there algorithms that simply give a YES/NO answer when solving an NP-complete problem without actually finding the solution. I'll answer both questions in this order.
(1) It is perfectly possible to solve a problem without brute force, i.e. without naively trying all possibilities. To take your example, modern complete SAT solvers can apply clever algorithms that infer or prove certain (partial) assignments can't lead to a solution, so they don't even examine that part.
More generally, even NP-hard problems often exhibit some kind of algorithmic foothold that allows us to design algorithm faster than brute force. The field of this research is exact (exponential) algorithms. Such algorithms take exponential time, but are still faster than naive algorithms. For instance, you can solve TSP in roughly $n!$ time, where $n$ is the number of cities to visit. This method won't scale to even moderate values of $n$, but there is a classic dynamic programming $O(2^nn^2)$ time algorithm due to Held & Karp. For general techniques, see e.g. branch & bound.
(2) There are "oracle algorithms" for NP-complete problems that just output YES/NO with no explicit certificate. For instance, consider the $k$-path problem:
(The $k$-path problem) Given a graph $G$ and an integer $k$, is there a simple path in $G$ on $k$ vertices?
The above problem is easily seen to be NP-complete. An $O^*(2^k)$ algorithm for the problem is given in [1]. The algorithm itself only gives a YES/NO answer to the problem, but we can use additional tricks to construct the actual $k$-path itself. More generally, when given such an "oracle algorithm", one can use tools from combinatorial group testing for extracting the witness itself.
[1] Williams, Ryan. "Finding paths of length $k$ in $O^*(2^k)$ time." Information Processing Letters 109.6 (2009): 315-318. publisher link, PDF
