If you can get your hands on a Japanese game that has a save file on it already (i.e. many second hand games), then you can use PKHeX and Pokémon Bank. A Japanese game fresh out the box will not work since the save game part of the data isn't initialised, and there's no way to replicate this without using a Japanese 3DS (by that I mean NTSC-J piece of hardware). Since it's pretty hard (and risky, in case the seller is lying) to get a Japanese copy of the game with a save file still on it, buying the console is what most people have to do.
No, the game cart and 3DS's region aren't determined by the language. Changing the language is purely aesthetic and it will not make it Japanese. If the cart is NTSC-J, it'll be accepted by the Cyber Gadget servers (since it's all done server side). If it's a game from any other region, it will fail to write the edited file to the cart. Again, there's no way to trick it. If it's a European cartridge it will always be a European cartridge.