When my son was 4 I gave him my Droid Incredible, which was deactivated when I upgraded. He liked it, and would play angry birds sometimes. He also took pictures (the camera isn't great but it's better than pretty much any kid's camera available) and listened to music on it. It was pretty impressive the way he customized the device, too.
My friend gave his son, who is a little younger, an iPod Touch and an iPad around the same time. I know his son uses his devices more than mine.
Contrary to the bulk of these responses, both children were up to the task of having and caring for a modern touchscreen device. You'll want to slap on a good case, and you need to know you can trust your child with it, but they're fine.
As for the recommendation... Well, this is an area where Android is playing catch-up with iOS. iOS has lots of parental controls so you can lock down default apps and prevent installation of unauthorized apps. I don't think either OS is particularly easier to learn, but the ability to control some aspects of the OS might make this an easier sell to the child's other parent, or just easier to monitor for you. If you get an Android device, I suggest you get one that can use the user profile features in Android 4.3 (it was added in 4.2 but there's more control in 4.3.)
However, I'm not sure a phone is really necessary. In fact, I think a phone would be more likely to be dragged around when not needed and more easily lost. It's more likely to become a nuisance. Since your son won't be with you, you have to consider the people he will be with. You don't want the device to become a problem and be taken away.
I would suggest an older device, this way it's less of a loss if it's broken or lost. At this point, you could easily get an older iPhone, iPod Touch, or iPad. A first generation Nexus 7 isn't a bad choice either. I'd go with one of the tablets, personally. They're better for video chats.