I'm pretty sure that you should be able to fight the first 11 bosses on your first playthrough. Maybe you didn't save between the final two bosses and that's why the second last doesn't appear (I'm pretty sure you must do this to get this fight on the first playthrough). I do know that you can't fight all 12 until hero mode though, sorry.