The standard linguistic approach to this problem is based on the phonological theory of features. The premise is that spoken language (the basis for rhyme) is a string of segments organized into syllables, and each segment is a network of "features", that is properties of sounds (such as "nasal", "labial", "voiced"). Various types of "rhyme" are based on identity relations between two words. The simplest case is "two identical syllables", meaning two syllables whose internal structure is the same, which means the segments are the same and in the same order. And then you check if the conjunction of features composing each corresponding segment are identical. There are zillions of kinds of rhyme, differing in which segments are subject to the identity requirement (alliteration is about syllable onset identity, assonance is about syllable nucleus identity, and so on).
Spelling gets involved because these days we read this stuff and don't hear it around the fire. Most rhymes were composed in the past and are just repeated over time. Owing to language change, a certain text might rhyme for one dialect but not for another. People can therefor disagree over whether X and Y rhyme. Hence the name of the Renaissance composer Dowland is assumed to be pronounced [do:land] and not [daʊland] despite modern practices, because it rhymes with (Latin) dolens.
The main impediment to computing probability of rhyme is dialect variation. The CMU dictionary provides a large supply of phonetically-notated words of "English" (including a lot of non-English words used by English speakers), and you can map their segmental notation (e.g. " EY1 ", " DH ") to standard features (see Introducing phonology for a list). You may want to manually adjust their pronunciations in case they give a bizarre transcription ('chutzpah' is given as [tʃatspɑ], lulz).
However, the vowels of "smog" and "dog", or "Mary, merry, marry" differ dialectally, so there will be disagreement over whether "Mary" and "merry" rhyme.
It is therefore a matter of personal judgment whether two words rhyme. You can use yourself as a judge and rest your algorithm aganst your judgments, or you can pick someone else to judge. If you try to extract rhyme from the extant corpus of all supposed rhymes (in English), the variability wall will be rather tall, but still, "cat" and "dog" don't rhyme anywhere.
