I built a plugin for Symfony 1.4 (PHP) to tackle this problem (among others). It is modeled after the way Django's test framework (Python) operates: the framework builds and populates a separate test database before each test starts, and it destroys the test database after each test completes.
I had a couple of concerns about this strategy, both in terms of performance (if the schema doesn't change, why not simply clear the data instead of rebuilding the entire structure?) and convenience (sometimes I want to inspect the database after a test failure, so don't destroy it indiscriminately!), so I took a slightly different approach.
Before the first test runs, the database is destroyed and rebuilt, in case there have been model changes since the last test. Before each subsequent test runs, the data in the database are cleared out, but the structure is not rebuilt (though a manual rebuild can be triggered from a test if necessary).
By selectively loading data fixtures in each test, one can create the proper environment for that test without interfering with subsequent tests. Fixture files can also be re-used, which makes this task much less onerous (though it is still my least favorite part of writing tests!).
In both test frameworks, the database adapter is configured to use the test connection instead of the "production" connection to prevent test execution from corrupting existing data.