Metaheuristic for NP-complete problem without exact algorithms other than brute-force
Thanks to user AdrianN (see comments) I was able to find a paper which presents a Mixed 0-1 Linear Program to find all Pure Nash Equilibria in n-player games. The method is an exact method and the authors provide performance results. 

Zhengtian Wu et al. “A Mixed 0-1 Linear Programming Approach to the Computation of All Pure-Strategy Nash Equilibria of a Finite n-Person Game in Normal Form”

This, however, only answers half the question.
This question remains: 


  Is it useful to design metaheuristic algorithms for a problem like
  this when its performance can not be shown by comparing it to other
  (exact) algorithms?


I realize this is a subjective question as, I think, D.W. tried to point out. I would like to answer this question myself by agreeing to D.W. and saying: It might be, it depends.

As a lot of references on metaheuristics will point out, it is important to be fully aware of the state-of-the-art before trying to design one. Metaheuristics tend to perform better than alternatives in certain (preferably interesting) situations, which should be shown by comparing them to said alternatives. Even if there is only a brute-force algorithm, it is likely that the brute-force algorithm will perform better in certain (interesting) situations and your metaheuristic will perform preferably much better in other situations. As D.W. said: "It depends what you're looking for, but sure, [metaheuristics] might be (useful), if you can accept the limitations."