Probable Origin
Elyse Bruce indicates the earliest example to be in "Jüdische Sprichwörter und Redensarten" (Jewish Proverbs and Idioms), by Ignaz Bernstein and B.W. Segel, Frankfurt, Germany 1908.
Sadly I'm unable to read the original German nor Yiddish, but the most likely version to be found there would be:
אויב מיין באָבע האט ווילז, זי 'ד ווערן אַ טראַמווייַ
Oyf mayn bobe hot vilz, zi 'd vern a tramvay.
If my grandmother had wheels, she'd have been a streetcar.
According to Adrienne E. Gusoff, the above is a less vulgar version of:
אויף מיין באָבע האט באַללס, זי וואָלט זייַן מיין זיידע
Oyf mayn bobe hot balls, zi volt zayn mayn zeyde.
If my grandmother had balls, she'd be my grandfather.
Select Examples
Some equivalents of both versions of the expression seem to crop up across Europe as well as in Israel and the US.
I apologize for failing to quote in this section. New users aren't allowed to post >2 url's, and all sources are - tragically - online.
Spanish
Si mi abuela tuviera ruedas, sería una bicicleta.
If my grandmother had wheels, she’d be a bicycle.
German
Wenn meine Großmutter Räder hätte, wär sie ein möbelwagen.
If my grandmother had wheels, she would be a van.
Hebrew
אם לסבתא היו גלגלים, היא הייתה אוטובוס
Im le-sávta hayú gálgalim, hi haitá otobús.
If grandmother had wheels, she'd be a bus.
Polish
Gdyby babcia miała wąsy, to byłaby dziadkiem.
If grandma had a mustache, she'd be a grandpa.
Dutch
Als mijn tante kloten had gehad dan was zij mijn oom.
If my aunt had balls, she'd be my uncle.
English
Ireland, American English (US, Midwest?)
If my aunt had balls, she'd be my uncle.
American English (US, Mayne/NY?)
If the queen had balls, she'd be the king.
American English (US)
If my aunt had wheels, she'd be a trolley.
Warning: the satirical website I linked is most likely NSFW, but it is hilarious :)
– laureapresa Feb 25 '15 at 07:33