You made a crucial change to the question. I've updated my answer to respond to the new question; I'll keep my original answer below for posterity as well.
To answer the latest iteration of the question: If the problem you really want to solve is a decision problem, and you've shown that it is NP-complete, then you might be in a tough spot. Here are some candidate next steps:
Look for heuristics. This means algorithms that work on some problem instances, but not all. Basically, you're hoping that you only come across problem instances that are easy, not any of the worst-case problem instances.
SAT solvers are an example of this approach. They solve a NP-complete decision problem ("does SAT formula $\varphi$ have a satisfying assignment?") using heuristics that happen to work well on many of the formulas we run into in real life, but their worst-case running time remains exponential. Integer linear programming is another example of this.
One very powerful kind of heuristic is to formulate your problem as an instance of SAT, ILP, constraint satisfaction programming, or something like that; and then apply an off-the-shelf SAT/ILP/CSP solver to solve it.
Look for a fixed-parameter tractable algorithm. Sometimes the complexity of a problem can be characterized by multiple parameters, and occasionally one can find an algorithm that is polynomial in one of the parameters, even if it is exponential in the length of the input (and thus is not a polynomial-time algorithm).
An example would be the knapsack problem, which takes as input an integer $W$ (the capacity of the knapsack) and some other inputs describing the items you can select from. The knapsack problem is NP-hard. However, there is a standard dynamic programming algorithm whose running time is $O(nW)$. This algorithm is exponential in the length of the input (because $W$ is specified in binary, so the value of $W$ is exponential in the length of the input), and thus this does not qualify as a polynomial-time algorithm. However, if $W$ is not too large -- as will often be the case in many practical settings -- this algorithm is efficient enough nonetheless.
Start looking at algorithms whose running time is exponential, or at least super-polynomial. Sometimes the running time can be optimized so that the exponential running time is (just barely) tolerable.
Change the problem. Start looking for way which you can "cheat", i.e., change the assumptions or the information given to you to make the computational problem easier.
Give up. Accept that this is one problem you probably won't be able to solve.
These are standard strategies for coping with NP-completeness. Many textbooks mention these options.
No, randomization alone is not going to take a NP-complete problem and make it easy to solve in polynomial time. Everyone knows that proving $P\ne NP$ is a famous hard problem, and that most complexity theorists expect that $P \ne NP$ but just don't know how to prove it; similarly, most complexity theorists expect that $BPP \ne NP$, but they just don't know how to prove it. Proving that $BPP \ne NP$ looks even harder than proving that $P \ne NP$. That's why it is the $P \ne NP$ problem that is famous, not the $BPP \ne NP$ problem; if we can't prove that $P \ne NP$, we have no hope of proving that $BPP \ne NP$.
Incidentally, many complexity theorists expect that $P = BPP$, but proving that is way beyond our current knowledge. That said, for all practical engineering purposes, you can assume that $P = BPP$. (Complexity theorists, close your eyes here. I'm about to use some engineering reasoning that works well enough for all engineering purposes, but will drive theorists crazy.) If you have an efficient randomized algorithm that solves some natural real-world problem, I bet I can build a deterministic algorithm that will almost surely solve the problem, too; I won't be able to give you a proof of that fact, but I'll gladly take that bet even at \$100 to \$1 odds in your favor. How can I be so confident? Because if we take your randomized algorithm and, instead of feeding it truly random bits, feed it bits from the output of a cryptographic-strength pseudorandom generator, then there's no way your randomized algorithm is going to be able to tell the difference. After all, if it could, it would have found a way to break the crypto. If you find a way to break the crypto, there are people who will pay you a whole lot more than \$100 for the secret. That's part of the reason why many people expect that $P = BPP$ (or some moral equivalent) is probably true.
Your original question said you wanted to find an approximate solution to a NP-complete problem, and asked what performance is possible. Here was my answer to that question:
It depends on the problem. Some NP-hard optimization problems have good approximation algorithms; others don't. There's lots written in textbooks (and in Wikipedia) on approximation algorithms for NP-hard problems; this is a standard topic in undergraduate algorithms. See, e.g., https://en.wikipedia.org/wiki/Approximation_algorithm and https://en.wikipedia.org/wiki/Polynomial_time_approximation_scheme, but make sure to read textbooks too.
BPP is not a relevant concept here. The question of whether $NP \subseteq BPP$ would be relevant if you were looking for a randomized algorithm that produces an exact solution to the NP-complete problem. But that's not what you're looking for. You're looking for a randomized algorithm that produces an approximate solution to the problem. Looking for an approximate solution is a different problem than looking for an exact solution. If there were a polytime randomized algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $NP \subseteq BPP$. Similarly, if there were a polytime deterministic algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $P=NP$.
Similarly, $PP$ is not very relevant here.
If you really want to relate this to complexity classes, the relevant complexity class is $APX$ (see, e.g., https://en.wikipedia.org/wiki/APX).
Incidentally, many approximation algorithms are deterministic algorithms. Randomization is occasionally helpful but often not needed.
