Can I/Should I cash it before obtaining the work permit?
Doesn't matter, if the work you're paid for is already done.
Do I pay taxes in the US as a slef-employed for these money? Technically I've earned these money before arrival.
If you're a cash based taxpayer (which almost any individual in the US is), you're taxed on the money when received. In this situation you receive the money when you receive the check (i.e.: you get the title for the money). Whether you converted the check to cash, or deposited it electronically, or assigned it to someone else - doesn't matter. Once you got the check - you got paid. If you got the check before moving to the US - you got paid outside the US.
Can I sign some kind of agreement on that, so these money would not be taxed in the US, because I've earned them outside of the US?
You can sign whatever you want, but it wouldn't affect the US government. If you're paid in November, when you are already a US tax resident, the US government will want its cut. See the definition of taxable income in the IRC Sec. 63. Unless you can find a way to exclude that income - it is taxable (and I can't think of a way).
In this case the client wants to postpone the recognition of the expense to the next year, so clearly the recognition of income would be postponed as well, they're symmetrical. You can't both double-dip on tax benefits.
What kind of accountant knows these things?
EA (Enrolled Agent), CPA (Certified Public Accountant) which is licensed in your State, or Attorney licensed in your State who's specializing in taxes. Noone else is allowed to render tax advice in the US (some other people are allowed to prepare tax returns, but not render advice).
A side note, as was mentioned by another user in the comments: you do not necessarily become US tax resident immediately when moving. You become US tax resident based on Green Card test (i.e.: once you become a lawful permanent resident) or substantial presence test (i.e.: once you stay in the US long enough). In some cases you can elect to be treated as resident, even if you don't pass these tests. So if you're not moving on an immigrant visa (which it sounds like you are, but we don't know for sure), you may end up being non-resident this year, and the question would be moot. See the IRS site on the determination of residency.