What is the filesystem used by Android external memory?
On Android 1.x/2.x, FAT32 (a.k.a., vfat). On Android 3.0+, I think that it varies, though it probably is ext4 on most devices.
Is it possible for me to recover deleted file(s) in either internal or external memory?
Possibly. It would be not significantly different than recovering deleted files from vfat or ext4 partitions on a Linux machine. Note that Android 1.x/2.x internal storage is YAFFS2, not vfat or ext4.
Is it possible for me to recover deleted messages?
There are many possible definitions of the English word "message". Most of relevance (SMS messages, email messages, instant messages) are managed by apps. There are probably tens of thousands of apps that handle "messages", and they will do so in thousands of different ways. Almost none of them are accessible to you, since very few will be open source.
Follow-up question for Q#2 and Q#3, can this be done without rooting/jailbreaking the phone?
No, with the exception of removable media (e.g., external storage implemented on Android 1.x/2.x as a micro SD card). You have no access to internal storage without rooting, and you do not have low-level access to external storage without rooting. "Jailbreaking" is not a term generally used with respect to Android devices.