Naja, so einfach wird das nicht werden, da ja auch innerhalb bestimmter Tags Zeilenumbrüche vorkommen können (z.B. in td oder p).
Als grobe Lösung würde ich den Text in
HTML- und nicht
HTML-Zeilen aufteilen (mit preg_split() bzw. preg_match_all()) und dann nl2br() auf den Nicht-
HTML-Teil anwenden.
Am besten wird dann wohl sein, dass du das ganze schon beim Eintragen machst, um die Page Generation Time nicht unnötig zu strapazieren...
Edit: @Khabarakh: Oder so. 