We introduce a project aimed at systematically searching for eXtremely Metal-Poor (XMP) very gas-rich blue dwarfs in voids in the nearby Universe. Several such galaxies were first identified in the course of an unbiased study of the galaxy population in the nearby Lynx-Cancer void. These very rare and unusual galaxies appear to be the best proxies for the so-called Very Young Galaxies (VYGs) defined recently in the model simulations by Tweed et al. (2018). We discuss the main properties of ten prototype objects residing in nearby voids and formulate criteria to search for similar dwarfs in other voids. The recently published sample of 1354 Nearby Void Galaxies (NVG) is used to identify a subsample of 60 void dwarf XMP candidates. We provide a list of these XMP candidates with their main parameters and finding charts. These candidates are the subjects of subsequent spectral, photometric and HI studies in the accompanying papers. Looking ahead, with reference to the submitted accompanying papers, we find that this study results in the discovery of many new XMP dwarfs with 12+log(O/H) ~ 7.0-7.3 dex.