Hi ! I am almost sure you missinterpreted the Team cherry interview, they use 64 pixels tiles for the blockout of the levels, that means they used just black squares of 64 pixels to create the walls/ground of the levels, and then, they placed the HD artwork on top of it manually ( this is my idea about how they created it ).
512 pixels for tiles is more than reasonable. You could even go higher without problem I am sure of it.
Regarding how I did this, I just used the Offset tool as you say, I just been doing tilesets for over a year so I have some practice.