These watches do use velcro, but they are not quite the same as the ones I was thinking of. These use velcro in order to seal the closure: the rest of the band is woven textile. There also are simpler velcro watch bands, where the velcro strip itself can be slipped under the pins, then you velcro the rest of it on. Sometimes they are labeled sports watch bands.
But this type of band would work well too, you are right. And @ClaudnDaye could measure the size of the band width on the Pebble watch and pick the band on that site.