I have a the following case. A client of mine had a domain name (registered to his company), but anyways the domain was arbitrated by another company that won it. The problem is that now we can't start a proper change of domain names with 301 redirects (because the domain is already redirected to the other company website) and the question is what's the best solution of this problem without losing too much traffic and rankings?
You essentially have already lost all of your traffic and rank. You are in effect, starting over. There is nothing you can do about it short of buying back the domain and I rather suspect that is unlikely.
Just deploy the website on your new domain and begin building back-links again. Create new PR where you had used PR sites in the past, and update any social media that you can. In your case, you will have to scramble twice as fast to out-pace the damage of losing the domain name versus starting a new site. But it can be done. But please expect that it will take as long to get back to where you were as it took to get there in the first place. It will not be easy or fast.