We can change the related list label from relationship field, but it'll change across all page layouts, can we have different related list labels for each of the page layout (based on record type assignment)?
Sadly, no, you (still!) cannot customize related list labels directly on their page layout. The label for a related list comes from the "Related List Label" field of the relationship field (lookup or master-detail field).
The only semi-workaround I could think of would involve using the translation workbench to translate the label into different "languages" (all English) to override the labels for groups of users assigned to those different "languages", but I really would not recommend that approach and it would probably have unwanted side effects / maintenance headaches.
About the only way you can have this level of granular UI customization as of today is with Visualforce. It wouldn't be particularly difficult to create related lists using standard Visualforce page block table functionality and use them as VF sections on a page layout, especially if you have a small number of related lists to do this with.
There might be more complexity depending on what factor you want to be the driving factor for the related list label change.
But if you have to do this for every related list on even a small number of page layouts, I suspect this would hardly be worth the trouble for most implementations.