Getting a job would be one solution, but couldn't you meet in some other country? I understand what you said about him coming to the US, but what's a few days in France?
In the meantime, what does your immigration solicitor say about applying for a fiancee visa? That shouldn't be a problem, although I suppose a recent visit (like in France) would probably help - you'd have that much more proof to show that you've been together, but, really, if you've met and have all that proof, you shouldn't have a problem.