Ancient Lichen requires a herbalist to be level 340 and can only be found in dungeons from the Outlands like Slave Pen,Underbog, Mana Tombs, Auchenai Crypts, Sethekk Halls, Shadow Labyrinth and The Steamvault. Gather Ancient Lichen can also give you Fel Lotus. Rogues and Druids are probably the best class to farm Ancient Lichen to avoid tough fights with mobs as they can stealth and sneak around. If you are using a higher level character then you can just storm in and solo the dungeon.
See below for ancient Lichen spawning spots in dungeons