Is queue button customization supported? Can I change the queue button's icon or behavior in Android Auto?

The icon used for the queue button is determined by the Android Auto app and there's no way for you as a developer to change that.

Alternative approaches? Should I disable the built-in queue and implement a custom solution?

The main option for being able to customize your app's appearance and behavior would be to build your app using the Car App Library, as detailed in Build templated media apps for cars. Note that media apps built using the Car App Library are (at this time) only supported by Android Auto (and not Android Automotive OS) and can only be distributed to Internal Testing and Closed Testing tracks on the Play Store.