Nice issue,
In order to recover the fields, I think that there is not more remedy than recreate them again. You'll have the old dictionary entries in "Deleted Records" modules.
Then, to recover the data, it would be great if you have them tracked by the history log ... I don't think History Log delete entries, due to, as far as I remember, the data is text.
If not, the best approach I think is to try to recover the old data from another instance, and, the last-last-last-last option is to ask for a backup restore in a third instance, and to move the data from the backup restored to the affected instance.
NOTE: Clones are made from the last backup done, so an easy and less traumatic option is to recover a clone, if since you deleted the fields and now, no backup has been done.
Good luck
