Many thanks to @A.B who filled in some missing pieces for me, especially regarding the semantics of netnsids. His PoC is very instructive. However, the crucial missing piece in his PoC is how to correlate a local netnsid to its globally unique network namespace inode number, because only then we can unambiguously connect the correct corresponding veth pairs.
To summarize and give a small Python example how to gather the information programmatically without having to rely on ip netns and its need to mount things: RTNETLINK actually returns the netnsid when querying for network interfaces. It's the IFLA_LINK_NETNSID attribute, which only appears in a link's info when needed. If it's not there, than it isn't needed.
The important lesson to take home is that a netnsid/IFLA_LINK_NETSID is only locally defined within the network namespace where you got it when asking RTNETLINK for link information. A netnsid with the same value gotten in a different network namespace might identify a different peer namespace, so be careful to not use the netnsid outside its namespace. But which uniquely identifyable network namespace (inode number) map to which netnsid?
As it turns out, a very recent version of lsns as of March 2018 is well capable to show the correct netnsid next to its network namespace inode number! So there is a way to map local netnsids to namespace inodes, but it is actually backwards! And it's more an oracle (with a lowercase ell) than a lookup: RTM_GETNSID needs a network namespace identifier either as a PID or FD (to the network namespace) and then returns the netnsid. See https://stackoverflow.com/questions/50196902/retrieving-the-netnsid-of-a-network-namespace-in-python for an example of how to ask the Linux network namespace oracle.
In consequence, you need to enumerate the available network namespaces (via /proc and/or /var/run/netns), then for a given veth network interface attach to the network namespace where you found it, ask for the netnsids of all the network namespaces you enumerated at the beginning (because you never know Beforehand which is which), and finally map the netnsid of the veth peer to the namespace inode number per the local map you created in stel 3 after attaching to the veth's namespace.