The village of Havering-atte-Bower, to the north of the borough, is the site of a long-lost royal manor house dating back before the Norman Conquest. Havering Palace was sited at what's now the highest point in East London, so had strategic importance, and was substantially upgraded in the 12th century. William the Conqueror, King John, Henry VIII and Charles I are amongst the monarchs who've lived or stayed here. If you've walked section 20 of the London Loop to the hilltop church at Havering-atte-Bower, you'll have passed through where it used to be. The borough of Havering isn't directly named after the palace itself, but after the privileged area that surrounded it.
The Royal Liberty of Havering was formed in 1465 on the orders of Edward IV, freeing the area from taxation and giving it independence in legal matters. It was originally equivalent to the parish of Hornchurch, which then stretcheddown through Romford and, narrowly, to the Thames. Magistrates convened at a court in Romford, while condemned criminals were hanged at what's now Gallows Corner. The manor house was in ruins by the 18th century, and sold off by the crown in 1828, but it wasn't until 1892 that the Liberty was formally absorbed back into Essex. The name 'Havering' was thus thought ideal when a new borough was proposed in the 1960s, as it covered much the same area, but with the addition of an extra strip east of the River Ingrebourne (including Rainham, Upminster and North Ockendon).
Newham
Out of all London's modern borough names, only Newham is a new word. The borough was formed by bolting together the County Borough of West Ham and the County Borough of East Ham, two of Essex's most heavily populated districts, formerly the Parish of West Ham and the Parish of East Ham. Both parishes were based around a 12th century church, namely All Saints in West Ham and St Mary Magdalene's in East Ham. Before the churches were built, and ecclesiastical division took place, these Thameside marshes were known only as Ham, an old English term for 'low-lying pasture'. What we now know as Newham, formed from West Ham and East Ham, was thus originally simply Ham (so could be deemed Oldham, but probably best not go there).
Redbridge
The borough of Wanstead and Woodford would much rather have amalgamated with Walthamstow and/or Leyton, but was eventually forced to join up with the borough of Ilford (because population totals added up better). To keep these new bedfellows sweet it was thought political to name the new borough after a feature on the boundary between them, even though that feature had been demolished forty years earlier. The Red Bridge was the sole crossing of the River Roding between Ilford Bridge and Woodford Bridge, a span supported on red bricks which carried a minorcountry lane deep into rural Essex. Along Redbridge Lane were Red Bridge House and The Old Red House pub. Then in 1922 along came Eastern Avenue, now the A12, and the old Red Bridge was swept away in favour of something majorly arterial.
The A12 thunders over the Roding fractionally to the north of the original bridge. The new crossing is not red, more concrete-edged, but retained the name Red Bridge on some old maps. When the Central line was dug in the late 1930s a new station was built close by, the original intention being to call it West Ilford. Planners then toyed with Red House, after the pub, then considered Red Bridge, but when the station finally opened after the war its given name was the single word Redbridge. And that's the name that's stuck, being awarded to the new borough in the early 60s (and the neighbouring Redbridge roundabout in 1977). No other London borough's name is so mired in etymological shadow.
Tower Hamlets
Like Havering, Tower Hamlets was another Liberty, but this time carved from Middlesex not Essex. It covered the area under the immediate influence of the Tower of London, a zone with military obligations to the Constable of the Tower (who had official powers to raise local forces to supplement his garrison). The Constable took the title Lord Lieutenant of the Tower Hamlets in 1660, with the surrounding 'county within a county' also known as the Tower Division. Amongst the incorporated hamlets were Whitechapel, Bethnal Green, Stepney, Bow and Poplar, as you'd expect, but also Shoreditch and Hackney. The original Tower Division was therefore rather larger than the borough of Tower Hamlets today, and included most of the current borough of Hackney (excluding Stoke Newington). It was officially dissolved in 1889 and absorbed into the County of London, but sort-of got its name back in 1965.
Waltham Forest
Waltham Forest was a royal hunting ground to the northeast of London, a particular favourite of Henry VIII, and was first named in the 13th century. It was one of four forests created when the larger Forestof Essex was disestablished, along with Hatfield Forest, Writtle Forest and Kingswood Forest (near Colchester). Waltham Forest was immense, incorporating both Epping Forest and Hainault Forest, and stretched all the way from Harlow-ish to Bow Bridge. The Waltham in question wasn't Walthamstow but Waltham Abbey, a Saxon settlement which doesn't fall within the modern borough. Walthamstow actually derives its name from the Old English word for welcome, not the forest, but those who named the boroughs must have appreciated the coincidence. Of all the names of all the London boroughs, Waltham Forest is historically the most diffuse.