Minor suggestion on the can_ok, based on some code I was recently writing:

no strict 'refs';
ok( defined *{$CLASS."::".$method}{CODE}, "$CLASS has $method")
[download]

At issue for testing is always whether a test really tests what you want. In this case, for example, can_ok $CLASS, $method isn't what you want if you want to know whether a method exists in a particular class. I find that test-driven development works for me because it makes me specify more clearly what behavior I want before I go write the code.

For the first general case you raise, my view is that one writes the test as soon as one knows what the expected behavior is. Until that's defined, playing around is OK. For the second case, while I've not had to tackle that kind of project, if I did, I'd approach it top-down, not bottom up. E.g., write a "total program" test that takes certain input and gives the actual existing output, then start to work on macro testing of major subsystems, etc.