Testing is hard in magento because of the structure and the "bad" design. Don't misunderstand me, the design is great - if you ask me, but it was not designed to test. Singletons are a no-go for testable code.
That said, you can do a lot of things with Ecomdev_PHPUnit:
Upgrade scripts in general
Testing upgrade scripts whether they do or don't work is hard. (afaik) the scripts run before the tests, so you can test the results. Does a attribute exist or was a table created. You can check, that the version of your module is correct and that the scripts exists. What you can't do (in my opinion) is to check the logic in the script.
Specifically upgrade scripts adding product attributes and the likes
As I said above, I think this is easy testable. You just test whether the things happen or didn't happen.
System xml and store config values
You can check for config values. And you can write controller tests to check the output of controllers. So you can check whether the default config value (or the one of the database) is correct and you can check whether the settings from the system.xml and the form fields are echoed.
Core rewrites
Not sure what you mean here.
Did you check \EcomDev_PHPUnit_Test_Case_Config::assertModelAlias, assertBlockAlias, etc.? You pass core/encryption to it and assert the expected class, e.g. Ikonoshirt_Pbkdf2_Model_Stub_CE. If your rewrite works, the test passes. If you have two competing rewrites, one of the test fails.
Controllers
Have a look into \EcomDev_PHPUnit_Test_Case_Controller.
