We performed a full mapping of the bulk electronic structure including the Fermi surface and Fermi-velocity distribution v(F)(k(F)) of tungsten. The 4D spectral function rho(E-B; k) in the entire bulk Brillouin zone and 6 eV binding-energy (E-B) interval was acquired in similar to 3 h thanks to a new multidimensional photoemission data-recording technique (combining full-field k-microscopy with time-of-flight parallel energy recording) and the high brilliance of the soft X-rays used. A direct comparison of bulk and surface spectral functions (taken at low photon energies) reveals a time-reversal-invariant surface state in a local bandgap in the (110)-projected bulk band structure. The surface state connects hole and electron pockets that would otherwise be separated by an indirect local bandgap. We confirmed its Dirac-like spin texture by spin-filtered momentum imaging. The measured 4D data array enables extraction of the 3D dispersion of all bands, all energy isosurfaces, electron velocities, hole or electron conductivity, effective mass and inner potential by simple algorithms without approximations. The high-Z bcc metals with large spin-orbit-induced bandgaps are discussed as candidates for topologically non-trivial surface states.