This depends on the programming language, the availability of a mocking framework and your need for mocking those complex objects. For C# and Java, there are frameworks available which allow you to mock out classes without creating interfaces first. (In the environment where I work, we don't use any of those frameworks, so whenever we have to mock a class for a unit test, we are going to create an interface.) In C++, you can avoid the need for interface-based mocking by injecting your "complex class" as a template parameter into every other component which is going to use it (the drawback is you have to templatize those classes, which means a certain amount of overhead).
In weakly typed languages there's often not even a language construct "interface" because you can replace an object of a class just by an object of a different type as long as the replacement fulfills the implicit contract (i.e. provides methods with correct names and signature).
Furthermore, I agree that DI does not work well with infrastructure classes like "strings". See this former PSE question & my answer to it.
I would like to add that your question sounds like "shall I always provide an interface 'just in case'". IMHO it is better to follow the YAGNI principle, start without an interface, and as soon as you need one, maybe for mocking purposes, refactor your code and introduce the interface afterwards.