Hi Steve,
I have no direct suggestions but just wanted to clarify two of your statements. You say that both John and Susannah were born in Birmingham. Is this just based on the 1841 Census or do have another source to corroborate this?
Secondly, have you seen the actual page from the parish register which fails to show his father's name or are you relying on a transcript? I assume from mckha's comment that an image of the register is available. Does the parish marriage register says whether John was 'of this parish'. Have you tried looking for the banns? Sorry if this all sounds patronising, but I am just trying to eliminate other options like trying to find the Bishop's Transcript for the marriage.
Do you know John's occupation? If he was a man with a trade there may be an apprenticeship record, or if he was earning reasonable wage and paying enough rent he may have been eligible to vote in the borough, and possibly parliamentary, elections so would appear in an electoral register (long shot I have to admit).
Have you compiled a list of all the John Greens born within the Birmingham area, (or preferably the whole of Warwickshire) for 2/3years either side of 1810, which you can follow up in the 1841 census to eliminate all or at least many of the others? In 1810 the population of Birmingham was still relatively small at around 100,000, but that population was fairly mobile as the new industries began to spring up, so there's no guarantee that John's parents originally came from Birmingham. And if he was their first born child his mother might well have returned to her mother's home to have the child. This was quite common at that time as it was safer to give birth that way than rely on a local, probably unqualified, midwife in a strange town.