I just verified our church's listing, but I can't remember exactly how I did it. I couldn't verify it via postcard because our mailing address is a PO Box and not the physical address. I couldn't verify it by phone because I don't own a mobile device. We already had a Map listing and I created a Google Page a few years ago, but never verified it. Recently we changed the name and website URL, so I used the 'Suggest an Edit' on Google Maps and somehow got it verified. Could be because I had the correct e-mail credentials for our Search Console and Google Page.
Jack of all trades, master of none.