This is a really interesting question. I don't think we're entirely happy with our approach, and we discuss it regularly, but these are our constraints and what we've done so far (framework has been in use for about 3 years).
1) We reload a skeleton database at the start of each test run. This has a minimal set of data, as little as possible - a user, minimal config. At one point we had an automated suite to generate this database regularly to ensure it stayed in sync.
- We don't reload the db for each test, because we don't want to slow down our test run.
- At the time we started the framework, the underlying database was changing quite rapidly, and writing SQL scripts to modify the db directly would have required a lot of maintenance. It is still changing, just not as rapidly.
2) The general approach is that tests create the data they need via the API (e.g. customers, orders, etc), and if they make breaking changes (e.g. to config), then they need to undo them at the end of the test. Being able to use the API to set up data rather than the UI makes this much faster to do at run time. We also know the data will be representative, as that's how the UI creates the data (for the most part) so we don't have to worry about our test data gradually diverging from real live data.
The issue we're facing now is that even the very minimal set of config that we have is restrictive - so we need to consider how we can generate different config, either by having multiple different skeletons, or by being able to modify that config at runtime.
It is pretty easy to run the tests on another machine with a different version of the database - we just need to set up the automation user, and change a few config settings (if they're needed by the subset of tests we're running). We have very little dependency on the actual underlying db design - you could change 99% of the tables, and as long as the application code still worked, we'd still be able to run our tests. This has meant that for example, we have been able to use the UI tests to detect issues when making database changes in areas that aren't well covered by integration tests. This might not be an issue for you.