A Fuchsian polyhedron is a hyperbolic 3-manifold homeomorphic to S_g x [0; 1] such that the boundary component S_g x {0} is geodesic and S_g x {1} is polyhedral. Here S_g is a closed surface of genus g>1. Fuchsian polyhedra are generalizations of hyperbolic polyhedra and constitute a toy family of examples of hyperbolic manifolds with polyhedral boundary. Ideal Fuchsian polyhedra (i.e., with vertices at "infinity") are related to questions in discrete conformality. We develop this connection and use variational techniques to show their rigidity with respect to the boundary (this is equivalent to the discrete uniformization theorem due to Gu-Guo-Luo-Sun-Wu). In the case of compact boundary we are able to obtain a kind of stability that allows us to prove the rigidity of Fuchsian manifolds with general convex boundary.