@Azah,
As a native speaker from the Northeast US.
Two nights ago...
The night before last...
Sound natural. (I would most likely say "two nights ago", but that's just me).
The night before yesterday
Sounds correct, but doesn't sound like something an American would say.
At night before yesterday
Seems incorrect (the "at" isn't correct).