update_user_meta() is what should assist you in doing this. Feed what get_users() returns and update the meta data for each and every one of them with the required values.
Assuming that you are going to store a serialized array, your custom query will have to unserialize each result in order to perform a search. I may not know the full extent of your intentions, but I hope this helps.