I am about to write a puzzle, but I don't know what type it should be. I think of Code Golf, but perhaps it needs to allow libraries. Then, I don't know whether and how much I should penalize the use of a library (e.g. triple your score if you used a library)
Can I initially omit the puzzle type, link to Meta to let people vote for a puzzle type (using predefined Community Wiki answers) and then later update the puzzle to define the actual type?
I don't think that's a good idea. Why would you post the question already if no one can actually answer it at that point (since the rules aren't even decided yet)?
This is exactly what the sandbox is for. You post the challenge spec there and include a couple of notes at the bottom about which things still need to be decided and what the options are. This way you can get some feedback from the community about the most reasonable choice. And if there are still arbitrary choices to be made you can use the comments on your proposal for polling. Once the challenge is finalised you can move it over to main.
See this FAQ post for more information about the sandbox.
You're also very welcome to join the chatroom to discuss challenge ideas, which is a bit more appropriate for extended discussion than comments in the sandbox, but even in that case it helps if you have the spec in the sandbox, so people have something to look at.
