I've learned that OP_CHECKMULTISIG is a Bitcoin builtin opcode to validate Multisig transactions. Can I write Bitcoin script to validate the Multisig transactions without invoking OP_CHECKMULTISIG? If so, what do I need to change in the redeemScript?
Yes, you can use a redeemScript that has a lot of OP_CHECKSIGs and boolean operations. You would have to enumerate all possible combinations of signatures however.
As a simple example, if you used a 2-of-2 multisig, traditionally your redeemScript would be
OP_2 <pubkey1> <pubkey2> OP_2 OP_CHECKMULTISIG
and the scriptSig is then
OP_0 <sig1> <sig2> <redeemScript>
Without OP_CHECKMULTISIG, your redeemScript would be
<pubkey1> OP_CHECKSIG OP_SWAP <pubkey2> OP_CHECKSIG OP_BOOLAND
and the scriptSig would be
<sig2> <sig1> <redeemScript>
For more complex multisigs with more keys and m-of-n, the scripts will be much more complicated with more OP_SWAPs, OP_BOOLORs, and OP_BOOLANDs.