The National Archives has a research leaflet on Tracing 18th and 20th century criminals and what records are available
http://www.nationalarchives.gov.uk/catalogue/RdLeaflet.asp?sLeafletID=120Survival of prison registers is very patchy, Winson Green especially and usually most prisons do not retain historical records.
Presumably Birmingham library checked the calendar of prisoners. He is also not showing in Warwickshire Record Office online calendar of prisoners.
http://www.warwickshire.gov.uk/Web/corporate/pages.nsf/Links/3C3BECFC9AF8FC7B80256E7E0056B9FEHowever the online index is not complete
'The series of Assize calendars is very incomplete at first. It starts with a few isolated calendars for prisoners held at Warwick Gaol (Summer 1801; Lent 1809; Lent 1829; Lent 1839; Lent 1841), but from 1849 to 1857, 1869 to 1871, 1874 to 1881 and 1888 to 1900 most calendars survive and have been indexed.
The calendars of Quarter Sessions prisoners are practically complete from 1800 to 1900, but the index does not at present cover the years 1836 to 1846 (with the exception of Epiphany 1836), and 1879 to 1884 (with the exception of Epiphany 1879 and Midsummer 1883).'So it might be worth checking with them on the calendars that have not yet been indexed or are missing.
If he was tried in an Assize court the records will be held at The National Archives (as the judges presiding at these courts travelled around the country and were government appointed. They tried the most serious cases). If at the quarter sessions the records will be held in a local record office - Warwick or Birmingham (local judges) .
There is just a chance he got a short custodial sentence at the Petty Sessions (Magistrates court). If they survive those records survive they will be held at Birmingham record office.
Regards
Valda