So, since nobody bothered to answer, I got a hold of an EU copy of AS, and ran it on my Japanese 3DS via homebrew. Starting the game via region free (which presumably forces the game to run on your region) didn't work, as MG simply said there was nothing there. Using HANS to force the EU region, however, got me Celebi's mystery gift.
So, decided to test something and tried my Japanese OR cartridge, using HANS to force an EU region, and sure enough mystery gift found the Celebi. Even after switching back to JP region the MG card was still there, and I got Celebi safe and sound.
In other words, with homebrew you can get the mythicals no matter what region game you have.