Changing an element in a list when a predicate holds
I'm not super familiar with Catan, having played it only once in my life and not even to completion, but a grid's a grid, and hex grids can be modeled using three axes instead of the usual two. The data structure you're searching for is an Array. (Or a Vector, if you wanna get fancy with mutability.)
Before I get to the demo, just a few notes on your various versions. #1 lies, if there's no match it just returns the first element in the array. The right thing to do is crash, or if you're feeling nice you can make your return value a Maybe Board. Returning the wrong thing is a good way to end up with subtle bugs that corrupt your data which you still just have to track down later, crashes get fixed. All your versions clobber any building that was already in that coordinate, which I have no idea if that's a thing that you do in Catan or not but I'm going to assume it's an illegal move.
These sorts of problems are easy to lose in the line noise when you haven't modeled your data correctly. One dimensional linked lists are great, but they're not the solution to everything. So, on to Arrays. You find them in the “array” package, which is part of the Haskell 2010 standard so you can expect it to be present in all modern compilers (GHC, GHC, and uh... GHC).
I've no idea what your vertex_coordinate :: ((Int, Int), Int) is supposed to represent (aside, use camelCase for your Haskell names, and did you intentionally choose a 2-tuple containing a 2-tuple over just using a 3-tuple?) but hexagonal grids are easy, especially hexagonally shaped ones like the Catan board is. Instead of just x- and y-coordinates, you use x-, y- and z-coordinates representing ↗, ↖, and ↓. Now the trick is to recognize that the axes aren't independent like in the Cartesian plane, they actually have a relation. Try drawing out a grid and figuring out what that is.
Hint:

 Remember that the origin is at \$(0,0,0)\$.

Solution:

 Using the arrows as given above for the positive direction of each axis, you'll notice that \$x + y + z = 0\$.

Now if I remember correctly Catan boards have a radius of 2, so we'll make an empty board.
type Coordinate = (Int, Int, Int)
type Board = Array Coordinate (Maybe Building)

emptyBoard :: Board
emptyBoard = listArray ((-2, -2, -2), (2, 2, 2)) (repeat Nothing)

And then write a place function that maintains the game logic.
placeBuilding :: Board -&gt; Coordinate -&gt; Building -&gt; Either String Board
placeBuilding board coord@(x, y, z) building
  | x + y + z /= 0 = Left &quot;Invalid coordinate&quot;
  | not (inRange (bounds board) coord) = Left &quot;Coordinate out of range&quot;
  | otherwise = case board ! coord of
    Just _ -&gt; Left &quot;Coordinate occupied&quot;
    Nothing -&gt; Right $ board // [(coord, Just building)]