How does ResNet bottleneck architecture's input size is possible to change from 56x56x64 to 56x56x356?
I do not know the answer for sure but I assume that the "256-d" refers to the shortcut connection and not the input. Since the output dimension of the 3 conv. layers in your right hand picture (fig. 5) is 256 the shortcut is transformed from depth 64 to depth 256. 

How this is being done is explained in the following paragraph on p. 4:


  Residual Network. Based on the above plain network, we
  insert shortcut connections (Fig. 3, right) which turn the
  network into its counterpart residual version. The identity
  shortcuts (Eqn.(1)) can be directly used when the input and
  output are of the same dimensions (solid line shortcuts in
  Fig. 3). When the dimensions increase (dotted line shortcuts
  in Fig. 3), we consider two options: (A) The shortcut still
  performs identity mapping, with extra zero entries padded
  for increasing dimensions. This option introduces no extra
  parameter; (B) The projection shortcut in Eqn.(2) is used to
  match dimensions (done by 1×1 convolutions). For both
  options, when the shortcuts go across feature maps of two
  sizes, they are performed with a stride of 2.


For ResNet-34 this not required for the first building block which is shown in fig. 5 but for later blocks too. This is shown by the dotted lines in figure 3: