This has more to do with /v/ being a voiced fricative than it being labiodental: note that the bilabial counterpart of /v/ is not /w/, but /β/, which is probably even rarer than /v/. Voiced fricatives as a group are a somewhat localized feature, as you can see on WALS. Even in languages that are listed as having /v/, it's not always clear that phonologically it should be analyzed as a voiced fricative, since it can pattern with approximants instead (or indeed, be realized as [ʋ]). This is the situation in Croatian, where /v/ is phonologically better seen as an approximant, and a voiced fricative only in dialects. Similarly, [v] or [ʋ] and [w] can be allophones of the same phoneme, which was probably the situation in Sanskrit, as it is in eg. Hindi.
Edit: as for how languages get to have /v/, a very reasonable development is b > β > v. This is what happened eg. in Modern Greek. Another possibility is allophonic intervocalic voicing of /f/, which later becomes phonemic. This happened in English, where the distinction was reinforced by a large number of borrowings.