Further info (mostly from the Warwickshire Herald or Harborne Herald) that I've come across about the Erdington Post Office, which could help to confirm/eliminate possible locations:
Mr S Taylor ran the Post Office in Erdington in the 1880s/90s. He was very active in Erdington, serving on various local civic committees.
The Post Office was situated two doors away from Mr W Pearson, the Chemist, in 1899.
In 1897, a watchmaker and silversmith named B. Runge had premises next door to the Post Office, Erdington
In 1889 and 1890, Erdington Post Office also had a lending library
In 1866, Mr E Sprawson, military haircutter, had premises located opposite the Post Office in Erdington.