When You can't Build Walls, destroy whatever "TownHall" they may have and start building one of yours.

Same with some other types of buildings such as Indian farms etc, so you can upgrade them.

As for Population, I found that Lower Tax + farms but also Fisheries will boost it up quite fast, so I know the temptation maybe Trade ports, however if you want more population Fisheries will help more, then when populations is higher, you can always destroy the Fisheries and build Trade ports or Shipyards instead.