Growing Manhattan Ameobas
Mathematica, 353 288 285 275 bytes

n=Input[];f@_=" ";g={z={0,0}};i=f@z=0;For[r=Range,i++&lt;n,g=Reap[(j=i;o={};For[d=0,j&gt;0,o=Rest@o,If[o=={},o=Join@@({e={#,d-#},-e,e={d-#,-#},-e}&amp;/@r@++d)];If[f[c=#&amp;@@o+#]==" ",f@c=i;Sow@c;--j]])&amp;/@g][[2,1]]];Riffle[(x=#;ToString@f@{x,#}&amp;/@m~r~M)&amp;/@r[m=Min@{g,0},M=Max@g],"
"]&lt;&gt;""


Ungolfed:

n = Input[];
f@_ = " ";
g = {z = {0, 0}};
i = f@z = 0;
For[r = Range, i++ &lt; n,
  g = Reap[(
        j = i;
        o = {}; 
        For[d = 0, j &gt; 0, o = Rest@o,
         If[o == {}, 

          o = Join @@ ({e = {#, d - #}, -e, e = {d - #, -#}, -e} &amp; /@  
              r@++d)
          ];  
         If[f[c = # &amp; @@ o + #] == " ",
          f@c = i;
          Sow@c;
          --j 
          ]   
         ]   
        ) &amp; /@ g
     ][[2, 1]] 
  ];  
Riffle[(
     x = #;
     ToString@f@{x, #} &amp; /@ m~r~M
     ) &amp; /@ r[m = Min@{g, 0}, 
    M = Max@g
    ], "
  "] &lt;&gt; ""


Here is an example output for n = 5:

      5
     5555     
    555555    
   5555555    
  555555555   
 55555555555  
5555554445555 
5555544444555 
 5555443305555
 55554432144555
 55555443234555
  5555544344555
   555554445555
    5555555555
      5555555 
       55555  
       55     


Input 8 takes about 4.5 minutes.

For a quick breakdown of my algorithm:

I'm using two look-up tables, f and g. The first one is just a sparse map containing the non-empty cells. The latter is a list containing all coordinate pairs for each cell-value (I think I don't even need to keep track of old ones here). I'm iterating through the coordinates in g to extend every cell from the last iteration. To do that I iterate over Manhattan distances, creating all possible vectors for each distance, and checking if the resulting cell is still empty (in which case I fill it). Repeat until enough new cells have been created.

When I'm done, I find the minimum and maximum coordinate in g and I create an appropriate grid, which is filled by looking up the cells in f. The rest is just joining everything into a single string with line breaks.