This can be answered more accurately using the whole trilogy; as Bootstrap (and Davy Jones) are elaborated on in the second and third movie.

First of all, I believe you are right in stating that:

• Either Bootstrap Bill must have been cursed
• Or Bootstrap Bill should not have been part of lifting the curse.

Since we know the latter to be false, the former must therefore be true.

However, I think there is a plausible series of events that avoids any plot holes. But I need to elaborate on some parts first.

1. Bootstrap Bill wants to be a sailor/pirate.

Regardless of the reason why, Bill left his son on land and resumed his life on the ocean. Bill is clearly a man who wishes to be out on the ocean; similar to Jack Sparrow (although Bill shows no ambition about becoming a captain).

2. The effect of the curse were not immediately clear to the pirates.

BARBOSSA
You idiot girl! It's no make-believe! My crew and I, we found the gold, and we did more than take one piece, we took it all. Rich men we were and we spent it and traded it and gave it away in exchange for drink and food and pleasant company.
But we found out: the drink could not sate us, and the food turned to ashes in our mouths, and no amount of pleasant company could ease our torment.

This means that between stealing the coins and docking at a harbor (for the women, drink and food), the pirates did not know they were cursed yet. Or else they wouldn't have tried.

PINTEL
Ah, William Turner. Stupid blighter. He threw in with us after we relieved Jack Sparrow of his captaincy, but turned out, it never sat well with him- particularly after we found Cortes' treasure, and its peculiar condition. He thought we deserved to be cursed, for leaving ol' Jack to the fate we did. That's why he sent off a piece of the treasure -- to you, as it were: so it would never be recovered, and so cursed we remain.

It seems that Bill stood up to Barbossa because he felt guilty for what they did to Jack.
But the curse from Cortes' treasure was the straw that broke the camel's back which caused Bill to stand up to Barbossa (and the other pirates)

Bill knew there was a curse on the gold, or he would not have sent the gold coin to his son so that he could curse everyone forever. However, it is not clear whether Bill (or any other pirate) was already aware of how bad the curse was.
Just because you believe you are cursed, does not mean that you think you are immortal. More likely, a curse causes you to die soon (because you are a magnet to bad luck or targeted by a supernatural force), you wouldn't automatically expect a curse to extend your life (which is a punishment in and of itself, of course).

If the pirates were not aware of their immortality yet, both Bill, Barbossa, and the pirates were all convinced that they murdered Bill by sending him to the bottom of the ocean.
He would be hanging there until he managed to free himself; but he wouldn't die. However, keep in mind that Bill possibly did not know that he was immortal at the time of sinking and assumed he was dying.

There are a few reason why Barbossa would do this to Bill. It's never made clear which one is the case:

• Barbossa doesn't believe in the curse (yet), so he does not think Bill cursed them forever. However, Bill is openly disobeying him, and Barbossa fears being the victim of a mutiny like the one he led against Jack Sparrow. Barbossa kills Bill to maintain order.
• Barbossa knows that Bill has cursed them forever. But he doesn't know about the immortality (yet). He drowns Bill because he wants him to die.
• Barbossa is aware of the immortality. He still drowns Bill, even though he knows it won't kill him. This could be done as a deterrent so that other pirates do not disobey Barbossa; or it could simply be done out of spite to imprison (immortal) Bill on the floor of the ocean for eternity.

3. Bootstrap Bill came to work for Davy Jones.

From what we see of Davy Jones, he offers to save people from death if they agree to work on his ship. So anyone who loves (or doesn't mind) sailing would take him up on his offer.

This means that Davy Jones has direct control over who lives and who dies (even if he can only temporarily prevent death). However, he only gives it to those who choose to serve him as a sailor on his ship.

Important to note here is that you do not need to have died to serve on Davy Jones' ship! Will, Bill's son, is the perfect example of this. He is alive while he serves on the Flying Dutchman under Davy Jones. Davy does not need to give immortality to those who serve under him. He simply gives it to them out of necessity, because they would usually be unable to serve him (usual = these men are dead already. Will is not usual)

The Flying Dutchman submerges itself when it travels between worlds; but Will is apparently capable of surviving these trips when he is on board. Although it is never explicitly stated, these trips are survivable by the living, not just the dead.

4. Pirates of the Carribean portrays the art of negotiation

It is an often recurring theme that deals between two parties can be made in such a way that no one technically lied, but the language was ambiguous and therefore a deal can be interpreted differently than how it was originally intended (by the duped party).

There are too many examples to elaborate here; but Barbossa and Elizabeth have a very clear example of this:

BARBOSSA
(comes to a decision) Very well. You hand [the golden coin] over, we'll put your town to our rudder.
ELIZABETH
Can I trust you?
BARBOSSA
It's you who invoked the parlay! Believe me, Miss, you'd best hand it over, now... or these be the last friendly words you'll hear!
Elizabeth hands over the golden coin.
BOSUN
Still the guns, and stow 'em! Signal the men, set the flags, and make good to clear port!
ELIZABETH
Wait! You must return me to shore! According to the rules of the Order of the Brethren -
BARBOSSA
First. Your return to shore was not part of our negotiations nor our agreement, and so I 'must' do nothing. Secondly: you must be a pirate for the pirate's code to apply. And you're not. And thirdly, the code is more what you'd call guidelines than actual rules.

While it is uncommon for pirates to completely ignore the deal they made, it happens very frequently that they intentionally phrase the deal in a way that they will get more out if it than the other party expects them to.

So here's my sequence of events that does not suffer from the plot holes that you are pointing out in your question:

1. Burdened by the guilt of what he did to Jack, and further burdened by the guilt of stealing a cursed treasure, Bootstrap Bill has a crisis of conscience and stands up to Barbossa.
2. For whatever reason (point 2), Barbossa drowns Bill. Regardless of Barbossa's knowledge, Bill did not know he was immortal.
3. Davy Jones is aware of what has happened to Bill. He brings him aboard, and gives him the usual deal: 100 years of servitude on his ship, in exchange for not dying. (point 3)

There are some possibilities about the deal between Davy Jones and Bill:

• Davy Jones may have been aware of Bill's immortality, while Bill is still unaware. Davy Jones chooses to keep Bill in the dark (negotiation - point 4) in order to increase his chances of Bill making a deal with Davy Jones. Bill, thinking that he is only alive by the grace of Davy Jones, accepts the deal because he does not want to die. Due to the edit below, this answer cannot be true.
• It's also possible that Bill was aware that he was immortal. He could have noticed when he stayed alive while sinking to the ocean floor; if it took Davy Jones a while to get to Bill. However, he still chooses to accept Davy's deal, because he wants to be a sailor (point 1) and even if he can ignore the deal and still remain alive (but cursed), he would still be a sailor without a ship. Bill needs a ship to serve on.

edit

As commented by ThievingSix below, Bill was at least aware of his immortality by the time he had sunk to the ocean bed.

They strapped me to a cannon, I ended up on the bottom of the ocean, the weight of the water crushing down on me. Unable to move...unable to die, Jack. And I thought that even the tiniest hope of escaping this fate...I would take it. I would trade anything for it.
?Bootstrap Bill Turner to Jack Sparrow

Whether he knew he was immortal when going in, I still can't say for sure. But he at least was aware of it while underwater.

The answer is in the first movie. It's revealed in a conversation between Will, Ragetti and Pintel. In this conversation, they say Bill intentionally sent the coin away, knowing that they were cursed. They also mention that he tells them what he has done. Barbossa furious over what he did, sends him to the bottom of the ocean. He is fully aware that Bill will not die, that is part of the beauty of the punishment. It's also revealed in the conversation that at this time, they didn't know all the requirements to remove the curse. Will Turner is an acceptable replacement, because he has Turner blood.

The sequence of events should roughly be as follows.

• On the way to claim the treasure, they maroon Jack.
• Not believing in curses they take the gold.
• They learn they are cursed, unable to die and so on.
• Bill decides to make the crew pay for their treachery by purposely getting rid of a piece of gold.
• He tells them what he has done and is strapped to a cannon and thrown overboard.
• They learn of the blood sacrifice, required to remove the curse.
• They continue looking for the gold piece and now a blood relative of Bill's.