Even humans bones regenerate at a slow rate. So Wolverine, as a mutant with healing factor-- his bones would regenerate, but at a considerably fast rate. As mentioned in a comment, without adamantium, his healing factor is even greater, as when it was in him, his body was constantly healing.
In the X-Men Origins: Wolverine movie, which you mentioned, he had his bone claws broken by Sabertooth before he had adamantium placed on his skeleton. It obviously grew back.
As mentioned in this answer, the The Muramasa Blade (the second one) is able to reduce Wolverine's healing efficiency.
Also see the question: How much of Wolverine has to be left to heal?