What I do in cases like this is change the encoding in the dbf file (part of the shapefile collection). This can be done with LibreOffice, for example. First make a backup copy of the original shapefile - all components. Then you open the dbf with LibreOffice, and specify Windows-1256 encoding. Then save back, but using UTF-8 encoding.
Now when you open the shapefile in QGIS, you should see the labels OK, without setting any special encoding. Then when you upload to the web, labels should appear properly.
I mention LibreOffice because 1)it's FOSS and 2)I think that new versions of MS Excel do not read *.dbf any longer. And the process for defining the output encoding is somewhat complicated.
If the attribute table became empty, then go back to the original *.dbf, try to open/ save and close without making any changes. And then check with QGIS.
And an additional comment: when you load/save a shapefile in QGIS there's an option to select the encoding. You mentioned that you change the encoding to WINDOWS-1256 when you read the shapefile. In a similar way you can save to a new shapeifle with "Save As..." and select UTF-8 encoding in the save dialog. Then use this new shapefile in Geoserver. This is probably the easiest.