PostgreSQL's trigram-comparing doesn't fare too badly, I think. The trigram functionality is inside module pg_trgm (a contrib module).

I compared your example sentences and asked pg_trgm what similarity it thought they had. pg_trgm expresses that similarity as a number between 0 and 1 (='very different' to 'virtually the same'):

           prior            | strict_word_similarity |           initi
+al part                
----------------------------+------------------------+----------------
+--------------------------
 (Identical)                |                      1 | And it came to 
+pass, when king Hezekia... 
 (Only punctuation differs) |                      1 | Thou shalt not 
+take the name of the LO...
 (Similar)                  |              0.8333333 | The fool hath s
+aid in his heart, There...
 (Should rank as similar)   |                    0.8 | Thou shalt not 
+steal.
 (Less similar)             |             0.45614034 | In the beginnin
+g God created the heave... 
(5 rows)

-- (column 3 truncated)
[download]

The SQL I used (the db must have pg_trgm installed, which you can do with CREATE EXTENSION pg_trgm;):

select 
     prior
-- , similarity(txt1, txt2)  
   , strict_word_similarity(txt1, txt2)  
   , substring(txt1, 1, 40) -- || chr(10) || txt2

from (values 
    ( '2 Kings 19:1'    , 'And it came to pass, when king Hezekiah hea
+rd it, that he rent his clothes, and covered himself with sackcloth, 
+and went into the house of the LORD.',
      'Isaiah 37:1'     , 'And it came to pass, when king Hezekiah hea
+rd it, that he rent his clothes, and covered himself with sackcloth, 
+and went into the house of the LORD.' ,
      '(Identical)')
  , ( 'Exodus 20:7', 'Thou shalt not take the name of the LORD thy God
+ in vain; for the LORD will not hold him guiltless that taketh his na
+me in vain.',
      'Deuteronomy 5:11', 'Thou shalt not take the name of the LORD th
+y God in vain: for the LORD will not hold him guiltless that taketh h
+is name in vain.',
      '(Only punctuation differs)' )
  ,
    ( 'Psalm 14:1'      , 'The fool hath said in his heart, There is n
+o God. They are corrupt, they have done abominable works, there is no
+ne that doeth good.',
      'Psalm 53:1'      , 'The fool hath said in his heart, There is n
+o God. Corrupt are they, and have done abominable iniquity: there is 
+none that doeth good.',
      '(Similar)' )
  ,
    ( 'Exodus 20:15'    , 'Thou shalt not steal.',
      'Deuteronomy 5:19', 'Neither shalt thou steal.',
      '(Should rank as similar)' )
  ,
    ( 'Genesis 1:1'     , 'In the beginning God created the heaven and
+ the earth.',
      'John 1:1'        , 'In the beginning was the Word, and the Word
+ was with God, and the Word was God.',
       '(Less similar)' )
) 
           as f(verse1, txt1, verse2, txt2, prior)
[download]