頑張ってみたけど、先読みを使うと、\r\nの時に都合が悪くて、
解決方法がわからんかったので置き換えでごり押し。

s/([^>])(\r\n|[\n\r])/$1<br>$2/sg;

改行コードを統一すると、先読みでもう少しスタイリッシュにかけた。

s/(?<!>)(?=\n)/<br>/sg;

何に使うかしらないけど、出力先のOSをみて改行コードを置き換えてもいいと思うんだけど。
サンプルは以下。

my @str = (
"<p>aiueo</p>\nkakikukeko\n<p>sasisuseso</p>\n",
"<p>aiueo</p>\rkakikukeko\r<p>sasisuseso</p>\r",
"<p>aiueo</p>\r\nkakikukeko\r\n<p>sasisuseso</p>\r\n",
);

foreach(@str){
s/([^>])(\r\n|[\n\r])/$1<br>$2/sg;
s/\r\n?/\n/g; # 表示確認のため、改行コードを\nで統一
print;
print "-------------\n";
}