When one deletes a Whatsapp (or other similar apps) message from a device (assume that no Google Drive, ICloud backup), can this message be recovered from the device? Does Whatsapp save messages into SQLite DB as normal text/unencrypted format?
Yes, it is possible, but like with many security questions it depends on the circumstances.
Generally the messages can't be recovered because WhatsApp state that they do not store chat histories on their servers.
If the message has been backed up using either iCloud Backup (for iOS devices) or Google Drive (for Android devices) then the message can be recovered when the user uninstalls WhatsApp and restores the backup.
To restore using the Google Drive method the user would need to restore to a local backup from the local WhatsApp database. This can be found in the WhatsApp > Database folder on the device. The filename is msgstore.db.crypt12 and there shoudl be various msgstore-YYYY-MM-DD.1.db.crypt12 files.
If the device is Android then it may also be possible to recover the message using a data recovery program such as Android Photo Recovery which utilises USB debugging mode to scan the device from a PC or a Mac.
Additionally to Mike Pooles answer, be aware that you sent this message to at least one other device.
If you don't have control over the other end device, it will be always possible to recover your message by acquiring the device or its backups.
Hiding the fact that you communicated with this party is difficult or even impossible because the metadata is available on the servers of Facebook, on the other end device and possible other third parties.