Onside kicks absolutely should be in the game.
How to do it? THAT"S the tricky question. With the current sim engine, I could see onside kick plays being pretty lulzy.
Might be best to handle it the same way that GLB used to handle FG and XP attempts... instead of simming an actual play, just have the sim run a simple calculation to see whether or not the onside kick "succeeded" or "failed." Base it on the kicker's Kicking, Vision and Confidence, aim for a range of 8%-12% success for the kicking team, and limit it so you can only attempt them if you're behind and the game is in Q4. Display it on the screen with an old-school style place-holder screen (just like the old FG/XP plays), and bingo: onside kicks.