Shined is indeed more common in American English than in British. It’s primarily used in the transitive senses, but you can also sometimes find shined in the intransitive, e.g., the stars shined in the night sky. (Source: MWDEU)
The Old English scinan is a strong verb. The weak form starts appearing in the early fourteenth century, and was well established by mid-century. Chaucer used both forms. From the General Prologue to The Canterbury Tales (line 198), saying of the monk:
His heed was balled, that shoon as any glas.
And from The Legend of Good Women, line 2194:
No man she saw, and yit shyned the mone.
Johnson’s 1755 dictionary lists both forms, giving priority to shone:
To SHINE. v. n. preterite I shone, I have shone; sometimes I shined, I have shined.
But by the late nineteenth century, shined was being frowned upon in educated use in Britain. It was never deprecated in US usage.
Pam Peters’s Cambridge Guide to Australian English Usage says shined is on the rise, increasingly used in metaphoric senses as well as transitive polishing.
(And professional shoe shines are available in London (I can’t speak to Australia on this point). They’re perhaps not as common as decades ago, but they’re there. Look in tube stops, bus, and airport terminals, or shopping arcades and malls that are frequented by business people.)