How to revise/resubmit a rejected article taking an unorthodox view
I certainly can't speak for all reviewers, and what I'm saying might be true only for me, but when I review a paper, I try to ask myself three questions: is it interesting for the venue? is it correct? is it improving the state-of-the-art? I need to be convinced that all answers are "yes", and the burden of convincing me is on the authors. 

A problem I've seen with some papers is that they focus mostly on showing the correctness of their approach, and at first glance, it seems to be the case with the paper you're describing.  Showing the interest of the approach is tricky, because often the authors are convinced it's interesting (otherwise, they probably wouldn't work on it), and they to think that everybody else understand why it's interesting. Similarly, explaining why it's improving the state-of-the-art might be tricky, especially for novel approaches, but it's necessary to explain why other approaches won't work. You have the right to write: "To the best of our knowledge, this approach has never been used to tackle this particular issue", but then, as a reviewer, I need to be convinced that your knowledge is good enough to make this kind of claim. 

Basically, in your situation, what you need is a compelling example (e.g., a situation/use-case where your approach is either the only viable one, or where you can show with experiments or formal proofs that yours is better than others). If you can focus on that point, then you can probably resubmit it to the same journal, but it's possible that you will get some of the same reviewers you had the first time. 

Another solution could be to publish the paper first as a technical report (e.g., on arXiv), try to submit it a short version without the proofs and technical details to a specialised workshop, where maybe you can get interesting feedback from the community (for instance, some recent related work), and then use that feedback to improve the paper.