I envy you being able to start this process from the beginning. I wish I could go back.
I certainly relied on spreadsheets extensively to refine my collection, decide which breeds I wanted to replace, but not to collect pets in the first place.
The main problem is that so many pets appear in so many zones. Some basic types like[pet] Rabbit[/pet], [pet]Rat[/pet], [pet]Roach[/pet], [pet]Adder[/pet] appear in many zones, making it very hard to work with a spreadsheet mapping pet to zone.
Instead, I would suggest the addon Rematch. Choose Filter / Other / Current Zone, and your pet list will display the pets available for the zone you are in. Now fly from zone to zone, and fill in the list of pets you haven't captured as you go.
Similarly, the addon Pet Tracker has a Zone Tracker option as well, that will highlight pets you don't have in this zone. I'd prefer Rematch for its functionality, but this can work too.
To make collecting easier, I would strongly advise you buy a Level 25 [pet]Grumpy[/pet] or [pet]Terrible Turnip[/pet]. Grumpy has[ability] Superbark[/ability], and the Turnip has [ability]Weakening Blow[/ability]. These let you reduce a target pet to 1 health for capture while guaranteed not to kill it.