View to show changes in node titles
You probably can't get 100% exactly what you want but you can get very close.  The problem is that we don't have a definitive history of the order in which revisions were created or edited.  You may be able to make some assumptions if, for example, you know that you always force the creation of a new revision any time an edit is made, but I don't know enough of your business logic to speak to that.  Regardless, I can get you most of the way there and build a view that shows nodes that currently have a title that differs from other revisions of the same node.

In my solution, you can end up with the following fields (amongst others):


Current Title 
Previous title
Date previously-titled-revision was last updated 
Date currently-titled revision was last updated


First, create a view based on Node Revisions.

When you do this I believe your view will, by default, have a relationship to the node table based on the vid.  It will be called "Content revision: Content".  You want to remove this.  There's another, identically named relationship that you actually want to add instead; it has a description that reads "Content revision: Content, The revision NID of the content revision."  Add that relationship.

After doing this you may find that you need to click on and re-save the settings for the "status" filter on the view as it will be set to use the old relationship. Or, if you want to see all nodes (even those that are un-published) just remove this filter entirely.

Now, add 2 fields to your view: 


Content Revision: Title -- this one probably already exists as it's added by default.  This is the title of the revision and can be considered "previous title" for your use-case.
Content: Title (this will use the relationship we just created) -- this is the title of whatever the "current" revision of the node is.  This can be considered "current title" for your use-case.


At this point, you should be seeing a list of all revisions of all nodes, regardless of whether the title has ever changed.  To limit the view to only show those where the title has changed we need to add a new filter called Global: Fields comparison.  Configure the filter such that the "Left Field" is set to "Content revision: Title" and the "Right Field" is set to "Content: Title".  Set the operator to "is not equal to".

Your view should now be more-or-less what you're looking for.  Feel free to add the appropriate date fields, though none of them will be able to tell you exactly when the title itself was changed, per se.

Also note that this will give you one row per different title a node has ever had.  So there may be multiple rows per node.