Refactoring without tests should be fine. From the cover of "Refactoring" by Martin Fowler: Refactoring is a controlled technique for improving the design of an existing code base. Its essence is applying a series of small behavior-preserving transformations, each of which "too small to be worth doing".
Fowler mentions in the introduction of the book that tests are necessary to find out if a refactoring didn't break anything.
Many unit tests that I've seen would count as tests that are too close to the current structure of the code.