Where do you get your stevia? I can only find powder and extracts, which I honestly think taste too much like their artificial counterparts (terrible). I haven't spent any time looking, but have been wanting to find a source for fresh or dried stevia to play with...
Your mix sounds really good. Does the basil not make the brew bitter?
At a herb class this summer I had and then started making at home a mix of lemon balm, mint, lemon basil and stevia. Very nice.
If the Stevia is making your tea taste metallic and artificially sweetened, you've used water that was too hot to steep it. Like Yerba Mate, boiling water bruises Stevia and causes the release of some rather unpleasantly flavoured bitter alkaloids. Try using water that's hot but not boiling next time, and you'll find that the bitter metallic taste disappears.
Depending on where you are, you shoud be able to find live plants at specialty nurseries - it's becoming a popular landscaping shrub in the US. If not, I can certainly send you dried leaves.