How can I get all my messages from before the phone was cleared?

If “Messages” was turned ON in Settings, your name, iCloud then no you cannot retrieve them.

If “Messages” was turned OFF in Settings, your name, iCloud then you can restore the entire most recent backup and lose everything else since that date. Without a daily iCloud backup that is probably not feasible.