It's possible to yank off one RJ45 and cross the cables, but you'd need a new one and a crimping tool to put the cable back together again. If you already have a straight through cable the best idea is to buy a little straight-crossover adaptor. I've seen these over here in the UK, for a very cheap price. Or you might be able to find the little adaptor you mention, which should work.
You could always cut the cable in half in the middle and connect using terminal blocks or a connection box. This may invalidate cat5 regulations, but it rarely makes a difference when you've only got two PCs.
I've always wired my own, but putting a standard RJ45 on the end of the cable is quite a skill.
In the end, the pin connections should be pin 1->3, 2->6, 3->1, 6->2 ...for crossover. Pin 1 is the left pin when the cable is pointing toward you, with pins upward.