Users will at least need the Limited Write People permission to perform this action.
From the left navigation select People > navigate to a persons profile > select the Actions dropdown in the top right of the profile > Edit Profile
The Edit Profile pop up will appear:
Select the Additional Tab > then click on the 3-dots menu to the right of the Record Type dropdown > choose Add New to create a new Record Type.
Note: You can also edit the list from this location. (i.e. change spelling, delete unneeded types)
Other Helpful Links:
How do I edit a person's profile?
How do I upload files to a person's profile?