How do I append a newline character for all lines except the last one?

Change your thought process from “append a line break all but the last time” to “prepend a line break all but the first time”:

boolean first = true;
StringBuilder builder = new StringBuilder();

for (Map.Entry<MyClass.Key,String> entry : data.entrySet()) {
    if (first) {
        first = false;
    } else {
        builder.append("\n"); // Or whatever break you want
    }
    builder.append(entry.key())
           .append(": ")
           .append(entry.value());
}