A ban is pretty harsh, how about taxing them heavily enough that they almost disappear? $1MM/billboard/year might be about right.
The reason people are asking for a ban of billboards is that they impose heavy externalities: they're distracting, ugly, et cetera. Capture those externalities rather than ban them.