It would most likely take a lot of hacking. FuSoYa did it to Secret of Evermore, and it took a massive amount of ASM hacking.

Difficult, yes. Near impossible, no. Of course, that assumes the hacker is an experianced ASM coder. (If they wheren't, I put it in the "near impossible" camp. However, you can learn "on the job" (I learned 6502 while hacking on SMBS), so who knows.)

As Nightcrawler says, the level of difficulty depends on how the game is organized. It could be (relatively) simple, or a complex nightmare. It all depends on how modular the game is, how similar the player controlled and AI controlled  character's control routines are, and other factors.

The starting point for such a hack would be to locate the player input routines and the AI routines. Where you would go from there is highly dependant on how they're structured, so it's difficult to generalize. If you're lucky, they'll do most of the work by calling a set of other routines that are shared between the two. In that case, it should be (relatively) simple.
If you're unlucky, they'll have very little common code, which would require much more work.