All of the history APIs used in browsing and Sync are already async, we should remove and replace all the remainig synchronous APIs. This may require some deep test rewriting, but we can do fake-sync wrappers for that.
I'll take it, but I'll need some help to get started.
I think you choose the hardest one, this will have to be splitted in a lot of smaller bugs, but don't want to scare you :) History changes (in form of visits addition or removal) in the browser UI are already using async APIs, but we have to convert all of nsIBrowserHistory and nsINavHistoryService (there also other interfaces, but those are mostly dependent on these and should be done later). A first dependent bug may be to deprecate addVisit and addPageWithDetails, that are used in a LOT of tests, to avoid rewriting all the tests we can likely write an addVisit wrapper that uses updatePlaces async API and spin the events loop till we get the callback. We should push people toward updatePlaces API. Related to this, we should rewrite the importExport service (bug 482911), hsivonen wanted to do that but he's likely really busy. If we kill any possibility to add visits synchronously, we can likely start converting nsIBrowserHistory the other methods, like removals. If you prefer starting from a smaller project, Favicons service has to be finished (is partially async) and has less connections to other services. Bug 672681 is another interesting entry point.
hm I said the importExport service, but I meant the migrators, whatever uses addPageWithDetails.
De-assigning myself in case someone wants to take it. Otherwise, I will eventually return to it.
This is basically a tracking bug, so making it properly that.