Pull up the old toilet, finish the tiling job, and drop in the new toilet. Anything else is going to leave you with a hack job that will eat away at your satisfaction in having your own home every time you turn around to flush.
Finishing the tiling job may turn out to be dead simple if matching tile is available. This is not likely, though, as anyone too lazy to pull the toilet when tiling a bathroom was probably also too cheap to buy tile from a reputable open stock.
So -- find some tile that co-ordinates with the existing floor. For example, if your tile has a pattern, pick up one of the pattern colors with a solid color. Or, you might like the effect of a solid color matching the new toilet.
Pull the old toilet. Enlarge the hole in the tile to a neat shape and fill it in with new tile. Make the replacement area just large enough to look like an expensive decorating consultant did it on purpose. Of course you might need a flange extender when installing the new toilet.
Now, to really finish off the look, find some other feature in the bathroom that can be highlighted in the same way. For example, you might re-color the area where you stand at the sink. Or, you could call out the door sweep area.
Save the removed tiles as well as any unused new tiles for future repair needs.
Is anyone in your family artistic and crafty? Use a combination of removed tiles and new tiles to decorate a tissue box.