What's a good mechanism to move from global state to patterns like dependency injection?

Background

I'm in the process of reworking and refactoring a huge codebase which was written with neither testability nor maintainability in mind. There is a lot of global/static state going on. A function needs a database connection, so it just conjures one up using a global static method: $conn = DatabaseManager::getConnection($connName);. Or it wants to load a file, so it does it using $fileContents = file_get_contents($hardCodedFilename);.

Much of this code does not have proper tests and has only ever been tested directly in production. So the first thing I am intending on doing is write unit tests, to ensure the functionality is correct after refactoring. Now sadly code like the examples above is barely unit testable, because none of the external dependencies (database connections, file handles, ...) can be properly mocked.

Abstraction

To work around this I have created very thin wrappers around for example the system functions, that can be used in places where non-mockable function calls were used before.

interface Time {
    /**
     * Returns the current time in seconds since the epoch.
     * @return int for example: 1380872620
     */
    public function current();
}

class SystemTime implements Time {
    public function current() {
        return time();
    }
}

These can be used in the code like so:

class TimeUser {
    /**
     * @var Time
     */
    private $time;

    /**
     * Prints out the current time.
     */
    public function tellsTime() {
        // before:
        echo time();

        // now:
        echo $this->time->current();
    }
}

Since the application only depends on the interface, I can replace it in a test with a mocked Time instance, which for example allows to predefine the value to return for the next call to current().

Injection

So far so basic. My actual question is how to get the proper instances into the classes that depend upon them. From my Understanding of Dependency injection, services are meant to be passed down by the application into the components that need them. Usually these services would be created in a {{main()}} method or at some other starting point and then strung along until they reach the components where they are needed.

This model likely works well when creating a new application from scratch, but for my situation it's less than ideal, since I want to move gradually to a better design. So I've come up with the following pattern, which automatically provides the old functionality while leaving me with the flexibility of substituting services.

class TimeUser {
    /**
     * @var Time
     */
    private $time;

    public function __construct(Time $time = null) {
        if ($time === null) {
            $time = new SystemTime();
        }

        $this->time = $time;
    }
}

A service can be passed into the constructor, allowing for mocking of the service in a test, yet during "regular" operation, the class knows how to create its own collaborators, providing a default functionality, identical to what was needed before.

Problem

I've been told that this approach is unclean and subverts the idea of dependency injection. I do understand that the true way would be to pass down dependencies, like outlined above, but I don't see anything wrong with this simpler approach. Keep in mind also that this is a huge system, where potentially hundreds of services would need to be created up front (Service locator would be an alternative, but for now I am trying to go this other direction).

Can someone shed some light onto this issue and provide some insight into what would be a better way to achieve a refactoring in my case?