Or alternatively, to use the same registration form but use visibility rules on the fields that appear according to the membership chosen by the visitor?
Yes, you can show/hide tabs/fields based off other fields values using CB Conditional. If by membership you mean a subscription provided by CBSubs then yes it's possible for plans to hide fields.
If visibility rules are used, can the forms make fields appear according to user's choice using ajax (without refreshing page)?
Yes, it's all done dynamically with no reloads.
Once the visitor has chosen a membership type and has submitted the filled out Registration Form, will he/she be registered accordingly? For instance, if in the field "Membership Type" he has chosen "Guest", will he be registered in the back end (MySQL) in the Users table as a Guest, etc?
I assume Membership Type is just a field so yes that'd be stored in the database as whatever type they selected. If you mean you want to assign a Joomla usergroup based off field value then you'll need CB Auto Actions for that, but it's certainly doable.