... ok, this is very simple...
To create a map larger than 256x256 in the world editor, you need to modify the editor to include larger map sizes on the list. To do that you should use MPQ injection. There are two utilities that exist which do this for you automagically:
Using either of those editors to create a map will
not make it incompatible with the normal world editor. You can simply create the map, save, close the special editor, and open the normal one.
There is another option, which is using the non-WorldEditor based map creation / editing utility that comes with WEU. If you uncheck pretty much all of the options in the map creation dialogue for this utility, you can create a large map that is compatible with the normal world editor. You can also edit the tileset with this utility, surpassing some of the limitations of the default world editor tileset editor. (still limited to the two cliffs which are native to the actual tileset you have chosen to use)
JASS NewGen also contains an in-editor advanced tileset editor, but it is quite a bit more advanced, requiring you to know the rawcodes for the tiles you wish to include.