The use case you have mentioned is imo best suited for Taxonomy.
Its in core.
For Point #1:
Create a Taxonomy vocabulary called "Product Categories".
Then add terms "Cars", "Motor Cycles", etc to it.
Now create child terms under Car's term, called Audi, Tayota etc.
After configuring your taxonomy. Add a term reference field to your content type ( say vehicle). Now you can associate your nodes with the taxonomy terms while creating Vehicle contents.
This approach is very flexible cause the relation hierarchy is maintained in a seperate interface and is not hardcoded into each nodes. Also you can have multiple term to which a particular vehicle belongs to. Like a vehicle can be in SUV subterm, as well as Cars.
I suggest using Taxonomy cause, it will handle the hierarchy ( the tree structure ) much better than node references. And you can leverage that while making views.
For Point #2:
You can us Taxonomy Menu ( a contributed Module ) to create teh menu item. Otherwise a view with display type Html List can also be used to list the terms ( and display count as well.. like Cars(36), Motor Cycles(22) ... and so on.
For Point #3:
Taxonomy automatically provides you pages to display content belonging to certain terms. To show related content you can leverage the help of Views. For example
Arguments -> Taxonomy: Term ID (with depth) will help you grab all the nodes belonging to child terms. Now i understand you dont want to show nodes, but Term.. this could be done by configuring field appropriately to show just the term name in views.
You may find the view export given in here very helpful.
For Point #4:
You get a default page for taxonomy term where it shows teaser of associated nodes. If that is not enough for your gallery, you can create a view for sub categories yourself, which takes term-id as argument.