1) You can jailbreak iOS 4.2.1. You can do this either by getting PwnageTool 4.2 and creating a custom .IPSW, restoring in Pwned DFU mode OR using the version of redsn0w that corresponds to iOS 4.2.1 -- I can't remember offhand what version it is, but redsn0w really is version specific. There is no known unlock for this baseband (though the Gevey SIM will work with it), but Sherif Hashim has tweeted that his latest exploit will work on the baseband you have, so if you hold off for just a bit, ultrasn0w 1.3 should unlock your phone as well, and more reliably than the Gevey SIM.
2) Yes, you can jailbreak and use the Gevey SIM. If it's the only solution you have then it'll have to work -- you've already encountered some of the Gevey SIM issues, so in a perfect world, you'll want to upgrade ultrasn0w when/if it supports your baseband and remove the Gevey SIM.
3) iClarified has tutorials on how to do it, just search for the iClarified Jailbreak Wizard. It'll ask you questions about your phone then give you step by step instructions.
4) The baseband you're referring to (iPad baseband 06.15.00) is NOT compatible with the iPhone4, it is ONLY compatible with the iPhone 3G/3GS. Any newer baseband on your phone will be a step backwards -- do not upgrade your phone's baseband now if you can possibly avoid it.
Important to note that the latest baseband (5.0.1) is NOT susceptible to the exploit that ultrasn0w 1.3 will be based on (or hasn't yet been announced to be supported, but heck, all of this is speculation at this point anyways). If you upgrade your baseband, you will lock your phone and it will be a long time before it can be soft-unlocked, so if you do end up upgrading your iOS to a newer version, ensure you use redsn0w or PwnageTool to block the baseband update. Unfortunately, the 06.15.00 iPad baseband is not an option that will work for you.
The people saying your phone can't be soft-unlocked are correct at present, but the people saying you can't jailbreak are not correct. Not only is 4.2.1 jailbreakable, but so is every version of iOS newer than it that is presently available -- all the way to 5.0.1. That said, DO NOT UPGRADE TO 5.0.1 unless you block the baseband update, I can't be any more clear that doing so will lock your phone AND block the Gevey SIM.