Banning existing billboards isn't a first amendment problem if it's not contingent on the contents of the billboard. Much like some radio frequencies are reserved, other media are forced to obey regulations.

>Doing it without compensation is a constitutional violation, and even if california modified it's constitution, it would be a federal one.

Only matters if the constitution is enforced. Courts can easily overturn previous decisions. If there's a will, there's a way.