Postgres - how to randomize two columns in a table
so that the locations stay accurate, but their association with a User
  is now random.


If I understand you right, it could work like this:

UPDATE tbl
SET lat = t.lat
  , lon = t.lon
FROM (
   SELECT t2.id, t1.lat, t1.lon
   FROM  (
      SELECT lat, lon, row_number() OVER () AS rn
      FROM   tbl t1
      ) t1
   JOIN  (
      SELECT id, row_number() OVER (ORDER BY random()) AS rn
      FROM   tbl t2
      ) t2 USING (rn)
   ) t
WHERE  tbl.id = t.id;


lat / lon have moved to another row, randomly. Every connection to it's original row is gone, but lat &amp; lon stay together.