I subscribe to your theory that Michael and Randy met while Randy was still human. They talked, exchanged names, that sort of thing. Somewhere in the process of Michael getting out of the Waterworks, his arm got "nearly broken off" and Randy got turned.

That was why Michael expressed such surprise in Season 2 when the zombies where trying to haul Tanya off and Michael spotted Zombie Randy. Michael thought Randy had died at the Waterworks.