What are the best ways to find an external thesis examiner? My supervisor is too busy to find an external examiner for my PhD thesis, so the job will probably fall to me. I know all the academics who may potentially be an internal examiner, but I don't know any academics outside of my own institution. To be honest, I do not know where to begin.

My area is computer science, but it overlaps with medicinal fields as well. There are presumably any number of people who would have some expertise in some part of my research, but very few who would cover all of them.

I feel that cold calling academics who are some way related to my research (maybe ones that I am citing in my thesis) asking if they will become my external examiner is a particularly poor strategy, but it is the only one that is apparent to me at the moment.
Start by going through the bibliography of your thesis draft.  For each author, consider whether they might reasonably be an external examiner (e.g. are they established scholars with a reasonable reputation, do they hold positions as professors in your discipline, etc.)  This should produce a large list of potential external examiners. 

I'd encourage you to get your advisor to contact prospective external examiners rather than contacting them yourself.