I have seen the Gaia project from here which is about mapping the stars in the Milky Way galaxy. But I'm wondering if there is any open data on the positions (or something like "positions" since it probably not calculable now), or "coordinates", of the galaxies in the visible universe, as opposed to the stars. I wonder how animations such as this (a time=1m30s point it shows the galaxies zooming out from the Milky Way) get their data on the positions of the galaxies.
There are lots of galaxy catalogs.
A classic all-sky galaxy catalog is the Third Reference Catalogue of Bright Galaxies (RC3, published in the early 1990s), which you can query here; if you follow the "FTP" links, you can find links to download the actual catalog.
(The HyperLEDA catalog that Dr. Chuck mentioned started as the RC3, but has various bits of data and re-classifications added more or less continuously since.)
A more recent catalog, based on the near-infrared observations of the 2 Micron All-Sky Survey (2MASS) is the 2MASS Galaxy Redshift Catalog, with about one million galaxies.
Even larger catalogs (though not covering the whole sky) can be found among the data products of the Sloan Digital Sky Survey, e.g. here
Many more catalogs exist, though some do not have accurate redshift information (meaning their distance from us is unknown or uncertain), and many are only for parts of the sky, sometimes very small regions (e.g., catalogs from Hubble Space Telescope observations).
(As for that video, I suspect very little is based on real data once you get beyond the Andromeda Galaxy...)
There is the Uppsala General Catalog of Galaxies
It has galaxies down to 19 magnitude. It doesn't have distances, but it does have radial velocity.
There is the HyperLeda catalog http://leda.univ-lyon1.fr/, which has about 5 million galaxies, with redshift for about 3 million (if I understand the summary).