@RedGrittyBrick is absolutely correct with his answer ("a router and a gateway are essentially the same"), some other responders are confusing the terms or, to put it kindly, have misunderstood the question (or wikipedia).
As far as routing goes the term "gateway" is almost only ever used in conjunction with "default", and that "gateway" provides a route to every network for which there is no more specific route available.
By definition then, the gateway must be a device that does routing, it could be a dedicated device, specifically a router, or a host which has been configured to route, but it is doing the same job. Thus a gateway can be a router and a router can be known as a gateway.
There is no difference in TTL between a "default gateway" and a router, once a device which is doing routing passes an IP packet from one network/subnet to another it must decrement the TTL, that is made quite clear in the relevant RFC.
A gateway need not be doing NAT, typically a home network will have a default gateway that is a router connected to ADSL, that type of device will do NAT, whereas the default gateway on your subnet at work will just lead to the wider office LAN and will not do NAT.
In answer to your question about getting out to somewhere that is not on the local subnet, @RedGrittyBrick is again correct about the ICMP redirects, in addition, the process that a host goes through when sending out a packet is this:
1 - Use own IP address and mask to check if destination packet's IP address is in local subnet.
2 - If destination in local subnet, send ARP request for MAC address of that local device then send frame to host.
3 - If destination not in local subnet, send ARP request for MAC address of gateway to that network then send frame to gateway for onward forwarding (at which point the point about ICMP redirects may kick in).
Thus it can be seen that every host makes a routing choice of its own prior to sending out packets (of course this data is cached so lookups are not occurring for every single packet).