Would that scheme be sound to implement ? Are there any flaws that would make it foolish ?

I believe it's sound.

I guess the most important thing to consider here is whether the salt generation is "random enough" to accommodate even the worst case (everyone has the same password)

A 256-bit random number is a good salt. It will never collide with another 256-bit random number anywhere, unless your RNG is broken. But a random salt is not enough.

If an attacker ever sees a signed challenge or gets the public key from the database, they can brute force the password that generates a matching key-pair. Therefore, the KDF should be a strong password based KDF, e.g. PBKDF2 with a high iteration count, or perhaps scrypt.

I used something similar in a (non-public) project. There the salt was generated by the server (because I wasn't sure clients had entropy), so it could even check that it didn't collide with any current salts. I used Ed25519 as the public key system; key generation from a seed is trivial for it.

Would that scheme be sound to implement ? Are there any flaws that would make it foolish ?

I believe it's sound.

Note that SRP is a proven authentication protocol that has similar security characteristics. It has more round-trips, though.

I guess the most important thing to consider here is whether the salt generation is "random enough" to accommodate even the worst case (everyone has the same password)

A 256-bit random number is a good salt. It will never collide with another 256-bit random number anywhere, unless your RNG is broken. But a random salt is not enough.

If an attacker ever sees a signed challenge or gets the public key from the database, they can brute force the password that generates a matching key-pair. Therefore, the KDF should be a strong password based KDF, e.g. PBKDF2 with a high iteration count, or perhaps scrypt.

I used something similar in a (non-public) project. There the salt was generated by the server (because I wasn't sure clients had entropy), so it could even check that it didn't collide with any current salts. I used Ed25519 as the public key system; key generation from a seed is trivial for it.