Is there a solution here that would allow me to provide him with a
debit card in his name that I could fund, that wouldn't have foreign
transaction fees associated with it (I'd probably be okay with a small
fixed ATM fee).
There are separate issues here. There is no law limiting bank accounts to U.S. citizens, but most banks will not open an account for a non-citizen outside their declared service area. There are substantial legal liabilities to the bank in allowing it, whether a citizen or non-citizen.
The difficulty will be compliance with the Patriot Act. This is an extension of the older "Know Your Customer" doctrine. It is improbable that the bank could comply with the Act without the potential customer being physically present. You would have to check with your bank in advance as to their policies. Banks are not required to accept a customer outside their policies.
As to waiving the foreign transaction fee, that is very improbable. Although a handful of institutions do this in specific cases it is uncommon because the bank isn't actually charging the fee, they are passing it along. With a credit card they collect interest and waiving the fee can be thought of as a reduction in interest income, that isn't possible on a debit card.
You would want to make sure you have a scrupulously honest nephew. You could be held criminally liable for any actions he takes at both the state and the federal level. U.S. law is global. A citizen who commits a crime in any country of the world can be charged for it in the United States. By being on the account you can acquire any liabilities that are created as an accomplice.
This is a bigger issue at the federal level because 4,000 federal laws do not require criminal intent. Some do not require you to even know the action happened. Unlike state law which generally requires you intended to commit a crime and had to be aware of it, federal law often does not. It is also not adequate that the action is legal in Russia if it would be illegal in the United States.
If I get a card in my name, and give it to him to use to withdraw money from ATMs, is that legal? What problems might that cause?
It is legal, but you are now strictly liable for its use. See the above answer. It would probably get shut down anyway when they phone you and asked: "are you in Russia right now?" The bank is still liable for you giving away the card. The bank may close out all your accounts and submit a currency transaction report on you to the Treasury for possible money laundering.
Wire the money. Plan out how much and when, but just wire it.