Castlevania's hardware setup would not allow you to switch tiles per scanline, that's more of a CHR ROM thing. (Because people can be pedantic, it can be done with CHR RAM, but not with the amount that Castlevania had.)
Using two separate palette to display a tile doesn't need extra tiles on NES, unless the tile would need to be "remapped". Like if you had a palette of black, brown, white. And a palette of green, dark green, light green.
If you wanted to display a tile using the green palette such that dark green was used where black was, you'd need two tiles. But if the second palette were dark green, green, light green (the same colors in a different order), you would not need a second tile to do that.
The forest and castle areas of the first level actually do use the same set of 128 tiles and palette. (Palette would be easy to change, though, they just just didn't.) I'm not saying don't use another set of tiles just because they didn't. Go for it. It's just information.
The HUD does not count towards your tiles. All reserved tiles are in one half, so the 128 you get are the other half.
The HUD does affect your palette choices, though. In Castlevania, the HUD always uses the same palette in every level (At least, so far. I'm beating it again to check, and I'll update this post if it changes. Edit: Doesn't change during gameplay).
For your mockups, you can have a different palette for the HUD so long as it remains readable. Battletoads changes its HUD colors per level to get the most out of its palettes. Castlevania doesn't, but it could.