Is it possible to play 2-player, 2-character Arkham Horror successfully?
Yes, We've played this way many times and it works quite well for an enjoyable game.  I highly recommend it.  You don't need to make any adjustment to the rules to do so, just make sure that you keep each character's possessions separate!  Also remember that certain game elements are based on the number of characters, not players.

One variation you might try is to play two people with one character each.  Just skip every other Mythos phase.  Essentially each character gets 2 turns between Mythos phases.  If you do this, consider yourselves to be playing a 4 character game for all relevant settings.  This will ease your bookkeeping headaches although it will also make the game a bit easier.

To address your statement that you find the game difficult under 4 people, you aren't the only one!  Here are the stats from 5200 games taken from the Arkham Horror statistics report.  If your winning percentage doesn't quite measure up to the below, keep in mind that folks submitting their games to this collection probably have quite a bit more experience playing Arkham Horror than most.


Investigators   Win %   Close % Seal %  Combat % Games
1               38%     3%      6%      29%      100
2               52%     4%      25%     23%      606
3               60%     7%      30%     23%      767
4               65%     11%     39%     15%      2,941
5               69%     16%     39%     14%      378
6               67%     16%     43%     7%       387
7               68%     16%     39%     14%      44
8               73%     25%     42%     7%       60


As you can see, as the investigator count decreases from 5, the game gets progressively tougher.  Also you will probably find more success if you are open to the possibility of a combat victory with 1-3 players