I'm not familiar with SQF but in the HACCP sense; anything where you're 'ensuring the effectiveness' once something is in operation is verification; validation is more about pre adoption trials, literature etc etc. So for the above examples I would say the following:
Observing employees during internal audit to ensure that they are meeting the requirements of your program - Verification
Interviewing employees to ensure that job training has bee effective and that key points are understood. - Verification
Using an external contractor to confirm that equipment is properly calibrated. - Possibly validation, on the fence on that one
Trending pest activity information to determine that the program is effective. - Verification
Environmental testing to ensure that microbiological loads are acceptable. - Verification
Validating the effectiveness of a metal detector by inserting a test piece into a product and confirming that the product is rejected. - Monitoring
So my suggestions for validating the above examples will be the following, and I'm by no means certain these are perfect examples; it's a tricky topic validating PRPs:
Internal audit - Train all auditors to an approved training package supplied by a company who has experience in training auditors and test the auditors at the end of the programme, then implement a shadowed auditing with new auditors until they have completed 2 audits for example. The training package, test results and shadowed audits would then be your validation.
Implement training programmes using trained competent staff to deliver the programmes, the content based upon a suitable text or texts (this could include standards, etc) and test the staff at the training programme. Again the source material reference and the testing would be your validation.
Calibration - as is, perhaps with some evidence from the manuals about why you chose your calibration frequency.
Pests - I would have some kind of risk assessment as the validation; that might sound a bit about face but you need to be able to justify what pest control you have chosen, the frequency of audit and the type and number of bait points etc to ensure the site is safe from pests as that is the validation part. (Ie you're chosing your pest control cover as to what you think your risks are.)
Cleaning - you need to do cleaning trials which are monitored then a high level of inspection and swabbing after them (as a trial exercise which you then write up) to ensure the methods used are effective. This would be your validation in conjunction with chemical specs etc. A lower level of environmental swabbing would then be verification.
Metal detection - the validation for this could be two fold; the specification and initial set up by the contractor (to say it can be effective and I've proven it is), and then some evidence for why you chose the test piece size you did (I often use the FDA hard and sharp contaminants document for this.)
For me, validation is about "why am I going to do this" so it must be an activity which could be achieved prior to that PRP, CCP etc being put into place. It might involve practical trials if there is no literature out there to support it but generally these are things you can do without being in full production, otherwise HACCP wouldn't work from day 1.