Best practices for re-clustering a broken cluster?

The best course of action would be to take one of the devices offline, re-create all of its objects on the device which is still online, clear the configuration on the offline device, create the basic configuration necessary to configure HA(VLANs and Self IPs), then configure HA between the devices.

Recreation of the objects does not have to be as tedious as it sounds. While I would not advocate making configuration changes directly to the /config/bigip.conf file, you can copy portions of that file such as the monitors, profiles, pools, and virtual servers into a new file, move it to the online BIG-IP, then use 'tmsh load /sys config file FILENAME merge' to merge the configuration from that file into the online BIG-IP.