Back in the 90s, the standard was that bright blue (#0000FF) meant unvisited links and a duller purple (around #800080, I think) meant visited links. Many users still associate various shades of bluish with links, and maybe some associated purple with visited links in particular. Google still follows the blue-and-purple practice, although they’ve wisely darken the blue for better sharpness, so the standard may still reside in some users' heads. If you have a shade of blue in your color scheme, use that for unvisited links, and try red-shifting it for visited, and see how it goes.
More generally, color coding of some kind is still advised to distinguished visited links. Try making unvisited links brighter (more saturation, more contrast with background) than visited links (paler or duller, depending on your background), to suggest the visited ones are “worn.” As long as the visited links aren’t gray (zero saturation), I think they’ll still seem active.
You can follow the usual procedures (e.g., see my calculations at Breaking the Color Code) to selected colors that are similar to each other (cohesive), while still being adequately distinct, accessible, and readable against your background.
Alternatives to Color
Using colors is semi-arbitrary, and thus can be difficult for users to discover. Using color can also disrupt the color scheme you're shooting for. Unfortunately, there probably isn't anything much better than color-coding for this. In my dreams, standardized icons with each link (with title/tooltips) would indicate (among other things) if the link was visited or not. For example, a visited link could have a check mark in its icon. However, without it being widely used by many sites, I don't think an icon would work well. The icons would have to be small, which would make them hard to recognize, and icons in general are hard to make understandable. It would take a lot of cut-and-try testing just to get an icon that is minimally helpful.
On the other hand, if you’re users regularly use your site, it might be worth developing the icons, and maybe including a legend on the site (in addition to the tooltips) to educate the users on the icons. This is especially the case if it's extra important for users to know what they have visited (e.g., some pages load slowly), or if it’s hard for them to mentally track where they’ve visited (e.g., lots of links, some pages having more than one link, links changing position (e.g., due to changing the sort criteria), or links changing names). If your users don’t regularly use your site, but it’s especially important to differentiate visited and unvisited links, it may worth the clutter of putting a straightforward text label like “(viewed)” after each visited link.